HG-News: News Headline Generation Based on a Generative Pre-Training Model

Neural headline generation models have recently shown great results since neural network methods have been applied to text summarization. In this paper, we focus on news headline generation. We propose a news headline generation model based on a generative pre-training model. In our model, we propose a rich features input module. The headline generation model we propose only contains a decoder incorporating the pointer mechanism and the n-gram language features, while other generation models use the encoder-decoder architecture. Experiments on news datasets show that our model achieves comparable results in the field of news headline generation.

I. INTRODUCTION
The aim of the text summarization is to condense a document while the condensed content retains the core meaning of the original document. The text summarization methods consist of extractive summarization and abstractive summarization. Headline generation is an abstractive summarization subtask, which is also called sentence summarization. In order to generate the headlines that compress the information in a longer text or a short text, we need to do the research about headline generation. We focus on the task of neural headline generation (NHG). An artificial neural network is used to solve the text generation task. Approaches using neural networks have shown promising results on the headline generation task which using an end-to-end model to encode a source document and then to decode it into a news headline. Most of the previous works are concerned with single document summarization, while this paper is only concerned with headline generation. The pioneering work of neural headline generation is [1], which uses the encoder-decoder framework to generate sentence-level summarization. With the development of the recurrent neural network (RNN) [2], [3] employed the attentive encoder-decoder model to sentence summarization.
The associate editor coordinating the review of this manuscript and approving it for publication was Xiaochun Cheng.
To represent the semantic better, a transformer was proposed [4]. Then, the transformer was employed for abstractive summarization [5], but the result was not improved compared with the attentive sequence-to-sequence model. OpenAI demonstrates that language models begin to learn the natural language processing tasks without any explicit supervision when trained on a new dataset. The model proposed by OpenAI is called GPT-2 [6]. Rothe developed a transformer-based sequence-to-sequence model with the pretraining BERT [7], GPT-2 and RoBERTa [8] checkpoints for sequence generation task [9]. In order to demonstrate the efficacy of the GPT-2 for the headline generation task, we don't leverage the checkpoints of the pre-training model but just use the structure of the GPT-2 model. Because most of the text summarization datasets are written in English, [10] proposed a large-scale short text summarization dataset. Currently, the whole summarization generation models use the encoder-decoder architecture to generate the summarization. We will attempt to only use the decoder to solve the headline generation task. In this paper, we conduct experiments on news datasets. We only employ the decoder model and the pointer mechanism for the headline generation task and incorporate the n-gram language information into the decoder. In our model, we propose a rich features input module. Moreover, we compare the experimental results based on the attentive sequence to the sequence model with our model.

II. BACKGROUND
In the task of headline generation, the input is represented as X , and the headline of the news article is represented as Y . X is equal to {x 1 , x 2 . . . , x m }, and Y is equal to {y 1 , y 2 , . . . , y n }, where n m. Specifically, the Y is only one sentence. Throughout this paper, x i represents the word in the article and y j represents the word in the summarization. The vocabulary list is represented as V = {w 1 , w 2 , . . . , w p }, and w k also represents a word. The p is limited to 50,000 in this paper.
In our headline generation model, we model where the θ is the model parameter.

A. TRADITIONAL FRAMEWORK OF NEWS HEADLINE GENERATION
The traditional news headline generation framework consists of five parts, which are shown in figure 1. In contrast to English news headline generation, the difference of the other language news headline generation is the tokenization. Given the input document, the tokenizer isolates the news document word by word. The encoder obtains the distributed representation of the document with the input word list X . Through the attention module, the distributed representation is recalculated. The decoder calculates the probability based on the word vocabulary list. With the greedy search or beam search method, we obtain the headline. The sequence-to-sequence generation model is shown in figure 2, which contains two parts. The first part is the encoder, and the second part is the decoder based on the attention mechanism. The input of the encoder is X . The encoder is a bi-directional long short-term memory(biLSTM), which generates the hidden state representation based on the one-hot representation of the input words. The biLSTM output is represented as (h 1 , h 2 , · · · , h i ). The first input word of the decoder is the <START> label. The decoder consists of a unidirectional long short-term memory(LSTM). In the training phase, the input of the decoder is the referenced headline.
In the testing phase, the input of the model is the word generated from the last step. The attentive distribution computation is the same as [2]. The equations are listed as equation 2 and equation 3, where Score is the function to get the attention feature between the target word and the source article words. At step t, the context representation is computed as equation 4. The attentionW is denoted as the attention weight. The h m is the output of the encoder, where h m ∈ R d e . The final distribution of the vocabulary at step t is computed as equation 5 and equation 6, where g is LSTM and f is constructed by LSTM and softmax. The s t represents the current hidden states of the decoder, where s t ∈ R d e . The symbol ; denotes the concat operation.

C. HEADLINE GENERATION BASED ON A GENERATIVE PRE-TRAINING MODEL
The transformer model proposed by [4] achieved state-ofthe-art performance on machine translation. Some studies have employed the transformer on English single document summarization, such as [5] and [11]. However, there is no research employing generative pre-training model (GPT2) [6], [12] on the news headline generation task. Therefore, in this paper, we gain insight into news headline generation by using GPT2. Our whole model is showned as figure 3 and figure 4. The news headline generation model consists of four parts: the input module of the news headline generation model, the convolution operation on the output of the input module, the GPT2 decoder model and a pointer-generator

1) INPUT MODULE OF THE NEWS HEADLINE GENERATION MODEL
The input module is defined as equation (7) and equation (8).
The input of news headline generation contains three parts: article words X , news headline words Y and a dilimiter character $ between X and Y . We embed all of the input words into a low-dimensional real-valued vector space with embedding matrix E ∈ R |V |×d e , where |V | is the vocabulary size and d e denotes the dimensionality of the words embeddings. We also embed the positional information into a low-dimensional real-valued vector space with a positional embedding matrix Pos ∈ R len×d e , where len is the maximum length of the position and d e denotes the dimensionality of positional embeddings. T ∈ R 4×d e is the token type embedding matrix. SI ∈ R 3×d e is the sentiment information embedding matrix. PT ∈ R 46×d e is the part of speech feature. The I is the output of the input module and the input of the generation model. The I ∈ R B×L×d e is defined as equation (8).
where B is the batch size of the training data, L is the sequence length of the input and d e is the dimension of the embedding representation.

2) DECODER BLOCK OF THE GENERATION MODEL
The decoder of the transformer is defined from equation (10) to equation (15). The attention_out is the result of the multihead attention, and H is the hidden state representation of the whole model. FeedForward is the one-dimensional convolution transformation.
where conv represents the convolution operation. where where where W ∈ R hd v ×d e .
where L 1 is the length of the source document and L 2 is the length of the target document. The multihead attention in the GPT2 model is differentiated from the transformer. One difference is the one-dimensional convolution of the attentive input, and the other difference is the concatenation of the current key and value with the past key and the value to avoid attenting to the repeat position of the input words.

3) POINTER MECHANISM IN HEADLINE GENERATION MODEL
In the short text generation model, there will also be an outof-vocabulary problem. To reduce the generation of out-ofvocabulary words, we employ the pointer-generator method used in [13]. We cannot use the pointer-generator model in our short text generation model, so we apply pointer mechanism defined from equation (18) to equation (21). To obtain the self-attention distribution, we transform the output hidden state H by a linear model and obtain the probability distribution by a softmax function, which is shown in equation (19). P_gen is the probability of choosing the word from the glossary, and 1 − P_gen is the probability of choosing the word from the source news article.

4) DECODER INCORPORATING N-GRAM LANGUAGE INFORMATION
In the GPT2 decoder, the vocabulary probability is determined only by the hidden outputs of the decoder block.
To obtain a more correct vocabulary distribution, we incorporate the language information into the input of the decoder block. We employ the 1-dimensional convolution method to obtain the 2-gram, 3-gram and 4-gram semantic information.
The convolution layer is defined in figure 5. The three kernel sizes we use are 2, 3 and 4. Through the three different convolutional filters, we can obtain the whole words representations. When calculating the vocabulary distribution, we incorporate the language information into the hidden states.

IV. RELATED WORK
Neural headline generation conceptualizes the task as a sequence-to-sequence problem or an encode-decode problem. The encoder maps the source word sequence to a distributed representation, and the decoder generates the target headline word-by-word given the distributed representation of the source sequence and the previously generated target words.
The first work to apply the neural network to text summarization was [1]. The attention based text summary model [1] was enhanced by a recurrent neural network [3]. The work of [14] also employed the attentive sequence-to-sequence architecture. The encoder used in [14] was the bidirectional GRU-RNN [15], which incorporated the features of the part of speech, name entity and TF-IDF, and the decoder was the unidirectional GRU-RNN [15]. To solve the outof-vocabulary problem, they also proposed a switching generator pointer model. Hu et al. [10] proposed a large-scale short text summarization dataset and conducted experiments on the dataset by using the attentive sequence-to-sequence model, but the experimental result was not good. To solve the problems of generating factual details inaccurately and repeatedly, [13] proposed using a pointer-generator network [16] and coverage mechanism to resolve these problems. To produce fluent summarization, [5] proposed to use the content selector to determine which part of the source document should be included in the summary. They conducted experiments by using bidirectional long short-term memory (BiLSTM) [17] and a transformer as the encoder and decoder. The work of [18] combined the abstractive method with extractive method and used a reinforcement learning method to bridge the nondifferentiable computation between these two methods. [19] first selected salient sentences by using reinforcement learning and then rewrote the selected sentence as the summary. The method of [20] used the convolutional sequence-to-sequence model and abstractive summarization achieved the state-of-the-art results in abstractive summarization field.
Recently, there are many researches in the field of the news headline generation [21]- [27]. The paper [21] presented a method for Nepali News Headline Generation. In the model they used the GRU as the encoder and the decoder. But they use the blue score as the evaluation criteria. Alexey and Ilya fine-tuned two pre-training transformer-based models for Russian news headline generation task [22]. In [23], they presented a Bengali news headline generation model based on RNN. The paper [24] presented a multiple headlines generation model and proposed a multi-source Transformer decoder. The paper [25] implemented a Myanmar news headline generation model based on LSTM. In paper [26], they proposed a model transformer(XL)-CC to generate headline and conducted experiments on the NYT datasets and Chinese LSCC news datasets. Wu et al. [27] proposed NewsBERT model on news recommendation dataset. The [11] showcased how pre-training bert model can be usefully applied in text summarization. All the headline generation models talked above employ the traditional encoder-decoder architecture while our model attempts to use the decoder only. The generation model with the decoder only can achieve the comparable results with the encoder-decoder models. We conduct the experiments on both the English datasets and Chinese datasets.

A. DATASETS
We evaluate the proposed approach on a news dataset [10]. This dataset is a large corpus of Chinese short text summarization dataset constructed from the Chinese microblogging website Sina Weibo. This corpus consists of over 2 million real Chinese short texts with short summaries given by the author of each text. The dataset consists of three parts. The first part is the main content of LCSTS that contains 2,400,591 training pairs. These pairs can be used to train supervised learning model for summary generation. The second part is the validation set, which contains 10,666 validation pairs. The third part is the testing set, which contains 1,106 testing pairs. In our experiments, we only use part I and part III of the datasets. Because the dataset contains empty content, we preprocess the dataset. After preprocessing, the training dataset contains 2,081,212 training pairs and 1,106 testing pairs. The average length of the article is 59, and the average length of the target title is 9.
The second dataset we use is XSum developed by Narayan et al. [28]. The XSum dataset consists of BBC articles and accompanying single sentence summaries. This dataset is a one-sentence summary dataset. The XSum dataset covers a wide variety of domains, such as News, Politics, Sports, Weather, Business, Technology, Science, Health, Family, Education, Entertainment and Arts. The XSum dataset is not diverse. This dataset is a single news outlet and a uniform summarization style. The summaries in this dataset are written professionally. The average length of the articles is 378, and the average length of the target title is 8. This dataset has 204,045 training pairs, 11,332 validation pairs and 11,334 testing pairs. We use the natural language toolkit to preprocess the text and get the sentiment information and the part of speech information.
To train the model better, we employ the Jieba tokenizer to tokenize Chinese articles.

B. IMPLEMENTATION DETAILS
We train our model on one machine with one Tesla V100 GPU. For all experiments, our model has 768-dimensional hidden states and 768-dimensional word embeddings. During training and testing time, the source article on the LCSTS is truncated to 80 tokens and the target title is truncated to 10 tokens. During training and testing time, the source article on XSum is truncated to 200 tokens and the target title is truncated to 10 tokens. The optimizer we use is the Adam optimizer [29] with β 1 = 0.9, β 2 = 0.998 and = 10 −9 . The vocabulary size is set to 50,000 for both source and target. The learning rate of the optimizer is set to 0.0003. The heads of self-attention are set to 8, and we employ a 6-layer decoder block.
During training, the batch size is set to 64. We train the model for 10 epochs because the dataset is too large. In the decoding process, we use the beam search method as the decoding search method. The beam size in the beam search method is set to 4.

C. EVALUATION
We evaluate the performance of our model by using the ROUGE metrics. On the datasets, we use standard ROUGE-1, ROUGE-2, and ROUGE-L [30] on full length F1. Unigram and bigram overlaps assess the informativeness, and ROUGE-L represents the headline fluency.

V. RESULTS
Our experiments results are shown from Table 1 to Table 4. Experiments are performed on the LCSTS dataset and the XSum dataset. The testing set on LCSTS consists of 1,106 sentences and 1,106 headlines. The testing set on the XSum consists of 11,334 sentences and 11,334 headlines.   On the LCSTS dataset, the baseline models we use include the RNN model [10] and RNN-context model [10]. The RNN model and RNN-context model experiments are conducted on the news headline generation dataset. The encoder of the RNN model is RNN, and the decoder of the RNN model is also a RNN. The RNN-context model uses the context as the input of the decoder. We re-implement the LSTM sequence to sequence generation model that incorporates the pointer mechanism and the coverage mechanism. The input of the model is the words or the characters. The experiment VOLUME 9, 2021 results are shown in Table 1. When the input is the characters, the vocabulary size is limited to 50,000. Our model is named HG-News. We only use the word-level input as the model input. In the HG-News model, we use the decoder only, and there is no encoder in our model. We also incorporate the pointer mechanism and n-gram language information into the HG-News model. Comparing to the pointer model [13], table 1 shows that the HG-news model achieves 2.19 points improvement on rouge-1 metric, 0.7 points improvement on rouge-2 metric and 2.46 points improvement on rouge-L metric. Because of the part of speech feature in the input data, the convolution layer in our model and the usage of the generative pre-training architecture incorporating the pointer mechanism, the news headline generation model we propose on LCSTS achieves comparable result with the other methods. Table 2 and table 3 show that the generation model with the transformer encoder is more effective than the generation models with other encoders.
On the XSum dataset, T-ConvS2S [28], which is a topic-aware convolutional variant of the sequence-tosequence model, is one of our baseline models. The transformer(6-layer)-LSTM model significantly outperforms the T-ConvS2S model. The model BertSumExtAbs [11] is a model based on pre-training model bert. Our model doesn't beat the BertSumExtAbs model on the Rouge-1 metric but beat the BertSumExtAbs model on the Rouge-2 and Rouge-L metrics. We conduct experiments with convolution layer condition, sentiment information and the part of speech information. When using the input data with the sentiment information and the part of speech information, our model improves 1.73 points on the Rouge-1 metric, 0.96 points on Rouge-2 metric and 1.74 points on Rouge-L metric. Table 2 shows the results with different encoders on LCSTS. Table 3 shows the results with different encoders on XSUM. Table 4 shows the results of our model on XSum compared with the baseline models. Table 2 and Table 3 show that the news headline generation model using the transformer as the encoder performs better than the news headline generation model with the embedding encoder and LSTM encoder. Table 4 shows that the news generation model based on the GPT2 model achieves comparable results compared with the baselines.

VI. ANALYSIS A. COMPARISON WITH EXTRACTIVE SUMMARIZATION
It is clear from Table 4 that the abstractive headline generation model achieves much higher ROUGE scores than the extractive system. The headline generation model HG-News we propose and the transformer-LSTM generation model beat the strong extractive lead baseline. Given these observations, we can provide some explanations as follows.
First, the first sentence in the news article contains some important information, which is proven by the lead result shown in Table 4. We found that using the first 80 tokens of the article on the xsum dataset yielded significantly higher ROUGE scores than using the first 400 tokens of the news article. The transformer encoder performs well in the short text.
Second, the abstractive headline generation model can beat the extractive lead baseline and the extractive systems because the title of the article is much shorter than other summarizations. The average length of the title of the news article is 8. The title generated by the abstractive systems achieves much higher ROUGE-2 and ROUGE-L scores than the ROUGE-1 scores. The abstractive headline generation model can produce coherent words and sentences adhering to the article.

B. THE RELATION BETWEEN THE CHINESE HEADLINE GENERATION MODEL AND ENGLISH HEADLINE GENERATION MODEL
Recently, many studies have combined the extractive method with the abstractive method. The extractive method can remove the unimportant information of the whole document, and then the abstractive method paraphrases the important words. In our headline generation model, we only paraphrase the news document. In contrast to other abstractive summarization models, we only use the decoder to train our headline generation model, while others simultaneously contain the encoder and decoder.
We conduct experiments on two datasets: a Chinese news dataset and an English news dataset. The average length of the article is 59 and the average length of the target title is 9. The average length of the articles is 378, and the average length of the target title is 8. We find that the length of the news article on the XSum dataset is much larger than that on the LCSTS dataset and that the length of the title is nearly the same on both datasets. We need to process the document with Chinese word segmentation in Chinese articles. Then, the training processing of the Chinese text is the same as that of the English text. Based on the lengths of the news articles and news headlines, we encode the articles with different steps and generate the headlines with different word length. Figure 6 shows the headline examples generated by the transformer-LSTM model on the two datasets. Examples of system summaries are shown in figure 6. We randomly select 2 documents from the testing dataset and compare the two kinds of results on the two models.

C. THE ABSTRACTIVE LEVEL OF OUR HEADLINE GENERATION MODEL
We have shown that our headline generation model is effective on a Chinese news dataset and an English news dataset. However, does the ease of the decoder mechanism make our system any less abstractive? Table 5 and Figure 7 show the proportion of novel n-grams that do not appear in the article for transformer-LSTM, T-CONVS2S and the HG-News model on the XSum test dataset. From Table 5, we can find that our model's titles and the transformer-LSTM titles contain a much lower rate of novel n-grams than the reference article titles, indicating a lower degree of abstraction. The gold result of the novel  n-gram proportion is different from [28], which may be caused by the difference in the text preprocessing process. Our HG-News model has a comparable degree of abstraction, which proves that our model is effective. Our model is not comparable to T-CONVS2S because the result of T-CONVS2S is much more different from ours.

VII. CONCLUSION
We propose a news headline generation model in this paper. The generation model is no longer a framework with an encoder-decoder structure. Our generation model has a decoder only. The attention mechanism in our model is multihead attention, which can obtain the semantic representation of the input tokens and obtain the attention distribution on the input tokens. In our news headline generation model, there is a rich feature input module which incorporates the sentiment feature and the part of speech feature into our model. We also present a pointer generation model to solve the out-of-vocabulary problem in the short text generation task. We also incorporate the n-gram language features into the hidden states. When generating a new word in the encoderdecoder model, the last token of the target words only focuses on the source tokens. In the model with decoder only, the current token of the target words cannot only focus on the source tokens but also focus on the generated tokens. The decoding process in our model is just like the human reading process which makes our model effective. The experimental results on the news headline generation datasets show that the model we propose achieves comparable results. However, there are also some problems in the news headline generation task; for example, the out-of-vocabulary problem cannot be avoided completely, and the word generated by the model sometimes is not correct. In the future, we will improve the capability of the feature representation and the accuracy probability of the word generation.


A Survey on Physarum Polycephalum Intelligent Foraging Behaviour and Bio-Inspired Applications

In recent years, research on Physarum polycephalum has become more popular after Nakagaki et al. (2000) performed their famous experiment showing that Physarum was able to find the shortest route through a maze. Subsequent researches have confirmed the ability of Physarum-inspired algorithms to solve a wide range of NP-hard problems. In contrast to previous reviews that either focus on biological aspects or bio-inspired applications, here we present a comprehensive review that highlights recent Physarum polycephalum biological aspects, mathematical models, and Physarum bio-inspired algorithms and their applications. The novelty of this review stems from our exploration of Physarum intelligent behaviour in competition settings. Further, we have presented our new model to simulate Physarum in competition, where multiple Physarum interact with each other and with their environments. The bio-inspired Physarum in competition algorithms proved to have great potentials for future research.

Introduction
Bio-inspired computing focuses on extracting computational models for problem solving from in-depth understanding of behaviour and mechanisms of biological systems. In recent years, cellular computational models based on the structure and the processes of living cells, such as bacterial colonies [43] and viral models [23] have become an important line of research in bio-inspired computing. Physarum-computing, as an example of cellular computing model, has attracted the attention of many researchers [82]. Physarum polycephalum (Physarum for short) is an example of plasmodial slime moulds that are classified as a fungus "Myxomycetes" [21]. In recent years, research on Physarum-inspired computing has become more popular since Nakagaki et al. (2000) performed their well-known experiments showing that Physarum was able to find the shortest route through a maze [57]. Recent research has confirmed the ability of Physarum-inspired algorithms to solve a wide range of problems [101,77].
Physarum can be modelled as a reaction-diffusion system (cytoplasmic liquid) encapsulated in an elastic growing membrane of actin-myosin cytoskeleton [2]. In the early stages of growth (i.e., the exploration phase), the Physarum foraging behaviour results in the generation of a branching pattern. In the second phase (i.e., the exploitation phase), it spans the sources of nutrients with a dynamic proximity graph and forms a pattern similar to Voronoi diagram [95]. This characteristic of continuous change in Physarum protoplasmic flux with the change of environment allows Physarum-inspired algorithms to have great potentials in dealing with graph-optimisation problems [101].
Computer scientists are investigating the potential of Physarum-inspired techniques for solving many NP-hard problems [5]. Physarum is capable of decision-making and information processing that can lead to the emergence of complex social behaviour [44,28,68]. It compares the relative qualities of multiple options and combines the information on reward in order to make correct and adaptive decisions. Physarum is also capable of memorising and anticipating repeated events, and displays both short and long term habituation, as a simple form of learning [19,20].
In deed, Physarum can be considered as one of the biological example of unconventional computation capable of creating a programmable Physarum machine [5]. It has been studied in the project "Physarum chip: growing computers from slime mould" [9] that ran between 2013 and 2016. The Physarum chip is expected to solve a wide range of computation tasks, including graph optimisation, logic and arithmetical computing [13]. The EU-funded project "Physarum Sensor: Biosensor for Citizen Scientists" is an extension of the PhyChip project [62]. This project showed that Physarum is an ideal biological substrate that could be used as biosensors that convert a biological response into an electrical signal. These low-cost biosensors can be used for various applications, including environmental monitoring and health [22]. Several reviews on Physarum have been published, however, they either focus on biological aspects [21,66] or mathematical models and bio-inspired applications [101,77,5,33]. The novelty of this review stems from a comprehensive survey that summarises the latest published literature on Physarum covering biological behaviour, reflection on modelling, and computing aspects. Further, we have covered Physarum-inspired applications from three aspects. In contrast to other Physarum review papers that focus mainly on Physarum-inspired algorithms to solve graph optimisation problems, we have discussed a second aspect of application which is taking advantage of Physarum characteristics, such as morphological diversity [34] and positive feedback loop [80], that will lead to the development of hybrid algorithms that optimise evolutionary algorithms to improve its efficiency and robustness [102,32]. In the third aspect of Physarum applications, we demonstrated Physarum as a method of biological computing that has been extensively studied in "Physarum chip: growing computers from slime mould" [9], and the PhySense project "Physarum Sensor: Biosensor for Citizen Scientists" [22].
In this review we have presented our novel model that simulate Physarum in competition settings. To the best of our knowledge, we are the first to explore Physarum intelligent behaviour in competition settings, unlike the other models based on a single Physarum. Multiple Physarum with autonomous behaviours react to each other and with their environment, this has allowed the efficient exploration of the whole system evolving to an optimal global network and each Physarum to move to a better position. Further, it has allowed us to deal with the increasingly proposed networks scenarios with multiple sources and multiple sinks. The bio-inspired Physarum competition algorithms proved to have great potentials in dealing with graph-optimisation problems in a dynamic environment as in Mobile Wireless Sensor Networks [16], and Discrete Multi-Objective Optimisation problems [17].
We will start by giving a short overview of bio-inspired computing (Section 2). For deep understanding of Physarum biological foraging behaviour we will review the biological aspects of Physarum including its intelligent foraging behaviour, collective swarm behaviour, and competitive behaviour (Sections 3, 4, 5, and 6). Then we will present some of the most well-known real biological experiments and mathematical models (Section 7 and Section 8). Furthermore, we will present some of the real-world applications that have been solved by Physarum-inspired algorithms (Section 9). Finally, a conclusion is given in Section 10.

Bio-inspired Computing
The inspiration from biology and nature has always been one of the most important and exhaustless sources for researchers and engineers to develop novel algorithms and innovative techniques during the past decades. Earlier works on bio-inspired computing focus on extracting the computational models from complex high-level biological systems of cognition and understanding. Under this umbrella of computational intelligence, there are many paradigms such as artificial neural networks, genetic algorithm, and artificial immune system. These models are based on imitating the behaviour of central nervous system, chromosomal reproduction, and immunity against infection, respectively [79]. In recent years, simple cellular computational models based on the structure and the processes of living cells became an essential branch of bio-inspired computing, such as bacterial colonies [43] and viral models [23]. Physarum is an example of a cellular computing model attracting researchers' attention [82].
Two typical categories of bio-inspired algorithms are evolutionary algorithms and swarm intelligence algorithms, which are inspired by the natural evolution and collective behaviour in swarms of animals, respectively [79]. However, there are several existing limitations of these optimisation methodologies [98]. Evolutionary algorithms use iterative progresses in a population in response to environmental pressure that causes natural selection, and this causes an increase in the fitness of the population. Genetic Algorithm (GA) [36] is an example of evolutionary algorithms. Swarm intelligence is one of the most exciting topics dealing with the collective behaviour of decentralised and self-organised biological systems. It consists of a population of simple agents which can communicate locally with each other and their local environment. These interactions can lead to the emergence of hugely complicated global behaviour [79]. A variety of swarm intelligence algorithms for optimisation problems, such as particle swarm optimisation [29], ant colony optimisation [25], and Artificial Bee Colony (ABC) [42], have been developed with increasingly wide applications in the real world.

Slime Mould (Physarum Polycephalum) Biology and Foraging Behaviour
Slime mould was classified as a fungus, a class of Myxomecetes, but now it is considered to be part of kingdom Protista. There are two main types of slime moulds: the cellular slime moulds, and the plasmodial slime moulds. The cellular slime moulds are formed of multiple cells, whereas the plasmodial slime moulds are formed of a large multi-nucleated single cell with thousands of nuclei without any membrane between them [66,21]. Physarum polycephalum (Physarum for simplicity) is an example of plasmodial slime moulds; it consists of a single cell amoeba-like organism and has a simple structure which can be easily modelled (compared to others like ants or bees). Physarum strains are not related to fungi and form a genuine branch in the evolution tree of life, other than fungi. More than 800 slime mould species exist worldwide [9]. This organism has a sophisticated life cycle ( Figure 1) [21]. The primitive intelligence of Physarum is mostly demonstrated during its vegetative stage when it turns into plasmodium. In this stage, it forms a yellowish vascular network which expands up to tens of centimetres in search of food to connect the food source (e.g., oat flakes) with the Physarum body [40]. Physarum can be considered as a parametric bio-blob that presents itself as a geometrically smart adaptive graph structure [95]. It is formed of a mycelial tubular network through which the chemical and physical signals, the nutrients, and the body mass are transported throughout the organism. The tubes of plasmodium Physarum are made of a gel-like outer membrane of actin-myosin cytoskeleton that generates periodic contractions of the tube walls. Inside this membrane, the cytoplasmic liquid is pumped back and forth in a rhythmically oscillating manner. The contraction amplitude and the frequency generally increase or decrease when encountering an attractant or repellent, respectively [27,89].
The Physarum senses gradients of chemoattractants and repellents and forms a yellowish vascular network in search of nutrition [27,90]. It responds to stimulation by changing patterns of electrical potential oscillations, and it is made of hundreds to thousands of biochemical oscillators [27]. A stimulus triggers the release of a signalling molecule cyclic adenosine monophosphate (cAMP) [26] that starts cytoplasmic streaming. This stimulus gives rise to propagating waves resulting in increased cytoplasmic streaming (shuttling) through that vein [27,89]. This generates a positive feedback loop; the higher the rate of cytoplasmic streaming is, the thicker the vein becomes [12].
The Physarum foraging behaviour consists of two simultaneous self-organised processes: expansion (exploration) and contraction (exploitation). Physarum structure reveals two distinct geometric patterns: (a) Physarum develops thin branches, searching in their environment for food, (b) the bulging droplet-like blobs enlargement at the tips of the branches [95]. In the early stages (exploration phase) the organism grows, and the branches with the bulging blobs at their tips become longer through the foraging process, and they divide into further branches and link up like veins. In the second phase (exploitation phase) the tubes that transport the nutrients will grow bigger while the tubes which do not transport enough nutrients will vanish and disappear [58,95].

Physarum Intelligent Behaviour
Physarum may not have a brain, but computer scientists are investigating its potential as novel, unconventional computers [5]. Physarum is capable of making complex foraging decisions based on trade-offs between risks, hunger level and food patch quality [44,45,28,69,96]. The primitive intelligence of Physarum Polycephalum (slime mould) is mostly demonstrated during its plasmodium stage (a large multi-nucleated single cell). The underlying mechanisms of Physarum intelligence and cognition are based on the way with which the organism perceives the environment, integrates this information and makes decisions [68]. This has motivated many researchers to take inspiration from their biological phenomena to come up with a novel, biologically inspired models for unconventional computational methods capable of solving many NP-hard problems [5]. In what follows we will summarise the Physarum intelligent behaviours.

Finding Shortest Path
This intelligent behaviour was first observed by Nakagaki et al. (2000) [57]. Physarum was able to find the shortest path between two selected points (source node, and sink node) in a maze-solving problem. Other examples of the shortest path approach may include the towers of Hanoi problem [64].

Building High-Quality Networks
Physarum's network design ability has attracted the attention of many researchers as it showed excellent ability in network construction without central consciousness during foraging process [7,19,68]. In the early stages (exploration phase) the organism's branches grow and the bulging blobs divide into further branches and link up like veins. In the second phase (exploitation phase) the organism eventually spans the sources of nutrients with a dynamic proximity graph (Voronoi pattern), where the links (edges) connect the corresponding nodes (vertices). This network architecture is highly dynamic with flexible rearrangement of its junctions, and once the Physarum moves, the location, size of the vertices and the edges changes, disappear, or new links and vertices (nodes) develop [95].
One of the most well-known real experiments that showed the intelligence of Physarum for network design was the reconstruction of Tokyo railway network designed by Physarum [82]. Some other real-world transportation networks have also been approximated by Physarum since then, such as Mexican highway [10], Iberian highway [8], Route 20 in USA [11] and Autobahn 7 in Germany [11].

Adapting to Changing Environments
Many biological experiments have shown that Physarum networks disassemble and reassemble within a period of a few hours in response to the change of external conditions (e.g., chemotaxis, phototaxis and thermotaxis) [37]. Moreover, Adamatzky (2009c) has shown that Plasmodium-based computing devices can be precisely controlled and shaped by illumination [4]. Jones et al. (2017) have demonstrated how a growth parameter in the model can be used to transit between Convex and Concave Hulls [41]. These results demonstrated how Physarum can approximate the external and internal shape of a set of points using chemo-attractant stimuli and masking by light illumination (repellent).

Physarum Collective Behaviour and Swarm Intelligence
Physarum exhibits swarm intelligence and social behaviour as social insects and animals. It shares with these insects and animals many common features of collective behaviour, such as synchronisation, communication, positive feedback, distributed intelligence, and spatial memory [66]. Physarum's collective behaviour is the result of communication and interactions among its individual units. Being a single-cell organism, Physarum individual units do not have a 'choice' to behave selfishly; rather, they communicate together via chemical transmitter namely cyclic adenosine monophosphate (cAMP) signals/oscillators which coordinate and synchronise Physarum's slug behaviour. A stimulus triggers the release of a signalling molecule cAMP that results in changing patterns of electrical potential oscillations which starts cytoplasmic streaming. This is distinct from other social animals such as bees or ants which use other types of communication (e.g., pheromone for ants) [66].
The following points will summarise the Physarum collective behaviour and swarm intelligence.

Synchronisation and Communication
The plasmodium (Physarum) shows synchronous oscillation of cytoplasm throughout all its parts that behave cooperatively for exploring the space, searching for nutrients, and optimising the network of streaming protoplasm. Each tiny oscillator is a segment of a tubule network, which is actively expanding and contracting as a form of distributed, collective behaviour that allows Physarum to make complex decisions when exploring its environment. This response causes the cytoplasm to flow in the direction of the attractant and away from repellent [90].

Feedback Mechanism
Physarum protoplasm migrates towards the area of the highest cAMP concentration and at the same time starts secreting cAMP. This behaviour creates a positive feedback loop, which will cause protoplasmic tubes with high cAMP levels to grow bigger and those with low cAMP levels to disappear gradually due to lack of flow [58]. The tubes that are more suitable for transporting the nutrients will grow bigger and will be of less resistance. On the other hand, the tubes which do not transport enough nutrients will eventually vanish and disappear. This feedback mechanism makes Physarum intelligent enough to maximise the number of nutrient sources and minimise transportation costs [58,95]. However, such positive feedback in Physarum is weaker than the ant colonies in the same maze problem, this will allow Physarum to discover and utilise new solutions and prevent the convergence on a single best solution [65].

Distributed Intelligence
Physarum may not have a central information processing unit like a brain, but rather a collection of similar parts of protoplasm. Physarum has recently emerged as a model system for studying information processing and problemsolving in non-neuronal organisms [61]. Physarum is a system describing the characteristics of a liquid geometry computer in conversation with its environment to survive [95]. This type of intelligence is now considered as a part of the theme "Liquid brains: How distributed cognitive architectures process information" [20]. Thus, Physarum is an excellent candidate for research on autonomous distributed network optimisation [72].

Memorising and Learning
Both learning and memory are essential features for animals to survive, and information on past experiences is used for optimal decision-making in a dynamic environment. Physarum is capable of memorising and anticipating repeated events. This intelligent behaviour was first revealed by   [69]. Moreover,  used an associate learning experiment to test this ability further [74]. Physarum secretes a trail of slime following movement, which acts as an extra-cellular spatial memory. This increases foraging efficiency of Physarum by avoiding previously explored areas [47,67]. Physarum displays both short and long-term habituation as a simple form of learning.
The information acquired during the habituation, even to chemical repellents, is via constrained absorption of these chemicals to be used as a "circulating memory" [20].

Physarum Competitive Foraging Behaviour
Competition Competition is generally considered as negative effects caused by the presence of competitors, usually leading to the reduction of available resources. However, competition can also yield lower overall costs, better quality, more choices and varieties, more innovation, greater efficiency, and productivity [30]. Competition can be classified into exploitation competition and exclusion competition based on the interactions of the competitors [92]. Exploitation competition happens when a resource that is in short supply is reduced by other competitors. This will negatively affect another competitors using the same resource. Only the more powerful competitors can obtain this limited opportunity. Exclusion competition regulates population density by slowing down the population increase if the population density is high and vice versa. Competition is very important in driving natural selection as a superior competitor can eliminate inferior ones from the area, resulting in competitive exclusion [54].

Physarum Foraging Behaviour in Competition Settings
There is increasing evidence that a simple organism like Physarum has complex social behaviours including cooperation and competition [45,53,71,73]. Physarum is capable of making complex foraging decisions based on trade-offs between risks, hunger level and food patch quality [45]. The skills of individual competitors are effective methods for inspiration to develop intelligent systems and to provide solutions for decision-making problems. Competitions between multiple Physarum is based on Physarum power (genotype), mass, and the availability of nearby food resources [71]. Physarum always initiates foraging behaviour quicker in the presence of competitors [76].
A recent study by Masui et al. (2018) [53] has provided an answer to a crucial question: can Physarum identify allogeneic individuals? The answer is yes, allorecognition implicitly promotes the Physarum's ability of to distinguish its own tissues from those of another, when encountering different individuals. In early research, people adopted the hypothesis that Plasmodium allorecognition was based on the premise of contact, and the slime sheath is just regarded as a simple repellent [67,88]. However, the recent study by Masui et al. (2018) [53] has indicated that the slime sheath is a substance that disperses allorecognition information about itself into the environment. This view led to a new self-extension model (Figure 2), in which the mechanism of non-contact allorecognition using a slime sheath expands the plasmodium opportunities for decision-making, which frequently enables early and safe avoidance rather than fusion [53].

Physarum Real Biological Experiments
Many experiments have been made to reveal Physarum intelligence. From a computer science point of view, the objective of creating such experiments is to build a mathematical model inspired by real biological experiments to solve real-world optimisation problems. We have summarised some of these biological experiments in Table 1.

Physarum solving maze experiment
Nakagaki et al. (2000) designed a biological experiment where a Physarum was capable of solving a maze [57]. The goal of the experiment was to demonstrate the intelligent behaviour of a single Physarum capable of finding the shortest path between two points. In this experiment, there was only one Physarum and one food resource (i.e., solving the shortest path problem).

Physarum network construction experiment
Tero et al. (2010) designed a biological experiment to simulate the Physarum network formation for the Tokyo railway network and other cities [82]. The goal of the experiment was to demonstrate the intelligent behaviour of a single Physarum (as a representation of Tokyo) capable of finding the minimum spanning tree that covers all points of multiple food resources (as a representation to other Japanese cities). Figure 2: Self-extension model with non-contact allorecognition. Self-extension occurs using the slime sheath as a signal transmitted to the environment, which facilitates non-contact allorecognition [53].

Physarum shape representation experiment
The behaviour of the plasmodium is mediated by environmental stimuli. Jones and Adamatzky (2014) demonstrated how a growth parameter in the model can be used to achieve transition between convex and concave hulls [40]. These results suggested novel mechanisms of morphological computation mediated by environmental stimuli and demonstrated how Physarum polycephalum can approximate the external and internal shape of a set of points using chemo-attractant stimuli and masking by light illumination.

Physarum living cellular automata experiment
The majority of these experiments have focused on Physarum behaviour in an open space (Petri dish). However, investigating the Physarum behaviour in a closed space will help us to understand how the organism makes its decision in a stepwise transition. To accomplish this goal, Shirakawa et al. (2015) have developed an experimental setup to discretise the motility of the plasmodium, and the motility was forced to be a stepwise one transition [75]. In this way the behaviour of the plasmodium was similar to that of a two-dimensional cellular automaton. They analysed the motility of only a single Physarum with no source of attraction (food source). They postulated several models (transition rules) of Physarum movement based on the statistical results of several experiment runs.

Physarum electrical activity experiment
Whiting et al., Traversa et al. (2014Traversa et al. ( , 2013) designed a real biological experiment where they measured the electrical activity of Physarum in the presence of stimuli (one food source) [97,84]. The goal of the experiment was to show how the Physarum changes patterns of its electrical activity when exposed to attractants and repellents, based on the fact that Physarum learn and adapt to periodic changes in its environment [47,67]. Gale [97]; where they presented a bio-inspired memristor-based circuit maze-solving approach.

Physarum solving the two-armed bandit problem experiment
The two-armed bandit problem has previously only been used to study organisms with brains. Yet Physarum, a brainless unicellular organism, showed the ability of decision-making and solved the two-armed bandit problem. In this experiment, Physarum was challenged with a choice between two deferentially rewarding environments, where the arm with the greater number of food resources or higher quality was designated as the high-quality (HQ) arm, and the other Physarum's ability to distinguish its own tissues from those of another (Allorecognition) 2 2 Petri dish Camera arm with fewer food resources or low quality was designated as the low-quality (LQ) arm ( Figure 3) [68]. The outcome of this experiment was to demonstrate the Physarum decision-making abilities. Physarum always chose the high-quality arm, and it can make multi-objective foraging decisions. It compares the relative qualities of multiple options and combines the information on reward (frequency and magnitude) in order to make correct and adaptive decisions. This experiment provides insight into the fundamental principles of Physarum decision-making and information processing.

Physarum foraging behaviour in competition settings experiment
Stirrup and Lusseau (2019) have designed a biological experiment to study the behaviour of Physarum under competition settings [76]. The experiment intercalated two Physarum in a common environment (petri dish) where there was only one food resource available. The experimental results showed that the time taken by Physarum to find food depends on their hunger motivation. However, the time taken for a Physarum to start looking for food depended on its motivation and the motivation of its competitor. Physarum always initiates foraging behaviour quicker in the presence of competitors.
In another biological experiment by Schumann et al. (2015), two strains were cultured in the same petri dish, the first was the usual Physarum Polycephalum plasmodium, and the second was another species called a Badhamiautricularis. Physarum Polycephalum definitely grows faster than Badhamiautricularis and overtakes more food resources, and could even grow into the branches of Badhamiautricularis, only if the Physarum inoculum was fatter (See Figure 4) [71]. Furthermore, if the invasive growth in front of Badhamiautricularis is well nourished by oat, it would easily   This avoidance behaviour was very clearly observed [53].
overgrow the opposing tube system of Physarum Polycephalum. Thus, competitions between Physarum Polycephalum and Badhamiautricularis is based on Physarum power (type), mass, and the availability of nearby food resources.
In a recent study by Masui et al. (2018) [53], five geographical strains of Physarum with different genotypes were collected. In each experiment, two individual plasmodia on oat flakes were placed on 2% agar in a round petri dish and were allowed to behave freely. Whether the individuals avoided or fused was recorded for all encounter cases. Allorecognition was defined as the time when the plasmodium came into contact with the other individual. Completion of allorecognition was defined as a change in behaviour (continuing straight, changing direction, or starting to fuse at the point of contact). The study has revealed that Physarum strictly identifies allogeneic individuals when encountering different individuals. The Allorecognition system in Physarum prioritises the avoidance and severely restricts fusion when encountering different individuals ( Figure 5) [53].

Mathematical models for simulating Physarum foraging behaviour
Physarum biological experiments are extremely slow and time-consuming to be applied in real-world network design problems. It is rather better to use the meta-heuristic algorithms inspired by Physarum intelligent behaviour (as conducted in real biological experiments) to construct mathematical models. The existing models are simulating the intelligent behaviour of single Physarum, and have overlooked foraging behaviour of multiple Physarum under competitive settings. For this reason, we have presented our new model to simulate Physarum in competition, where multiple Physarum interact with each other and with their environments. We have summarised some of these existing mathematical models in Table 2.
The flow-conductivity model The flow-conductivity model is based on Hagen-Poiseuille Law and Kirchhoff Law to describe the adaptive feature of path finding and the feedback between flux and conductivity of the protoplasm tubes [81,55,83]. Experiments on Physarum led by Nakagaki and Guy (2008) have proposed the mechanism of protoplasmic flow through Physarum's tubular veins, which is believed to account for Physarum's intelligence [55]. The flow-conductivity model was first proposed by Tero et al. (2007) and  to simulate Physarum foraging behaviour [81,83]. This model can solve the shortest path-finding and the maze-solving process of Physarum. The model illustrates the feedback between the flux and the thick of protoplasmic tubes; first, open-ended tubes, which are not connected between the two food sources, are likely to disappear. Second, when two or more tubes connect the same two food sources, the longer tube is likely to disappear. The model was applied in dynamic navigation to design the railway network around Tokyo [82].
In this model, two terminals are representing Physarum (source/node), and the other terminal is food resource (sink/node). The protoplasm flows in every edge from the source node to the sink node. There is a pressure at each vertex, and the quantity of flux in each edge is proportional to the pressure difference between the two ends of these edges. Specifically, the flux Q ij in edge (i, j) is given by the Hagen-Poiseuille equation below.
where D ij is the edge conductivity, c ij is the edge length, p i and p j are pressures at vertices i and j, r ij is the edge radius, and ξ is the viscosity coefficient.

Reaction-diffusion model
Adamatzky (2007) regards the Physarum as an encapsulated reaction-diffusion computer, and utilises a two-variable Oregonator equation to simulate the Physarum spanning tree construction [2,1]. In this model, the wavefront is used to simulate the motion of Physarum, whose trajectory is steered by the gradient of chemo-attractants. It was treated as a bio-realised unconventional computer called "Physarum Machine" to solve maze problems, graph problems and design logical gates [5].

The cellular model
The cellular model was proposed by Gunji et al. (2008) [34]. Given a planar lattice, and every lattice site has various states: the inside (state 1) is surrounded by a boundary (state 2) in a lattice outside (state 0). In the foraging phase, there is cell invasion of the outside with softening of the membrane of Physarum. The protoplasmic flow toward the softened area, which leads to a re-organisation of the distribution of the cytoskeleton. This model was applied to simulate the amoebic motion and solve the classical Steiner tree problem in planes [34,35]. Moreover, other researchers have developed a cellular automata model based on reaction diffusion to simulate the behaviour of Physarum [85,86,51].
The multi-agent model Jones (2009) has been proposed a multi-agent, where Physarum is thought to consist of a population of particle-like agents [38]. Each agent senses and deposits trails as it moves towards the nearby stimulus within a 2D diffusive lattice. In this model, the structure of the Physarum network is indicated by the collective pattern of the positions of agents, and the protoplasmic flow is represented by the collective movement of agents. Furthermore, Wu et al. (2012) improved the initial multi-agent model by adding a memory module to each agent [99]. This improved model is more flexible and adaptive, and it approximates the behaviours of Physarum more closely.
Liu et al. (2017b) proposed a self-organised system modelling approach in which two types of agents are used for simulating both the search (exploration) and the contraction (exploitation) of Physarum in foraging behaviours [49]. In this model, the body comprises a synthesis module and a motion module, and each sensor is armed with a trail sampling module and a chemo-nutrient sampling module.

Physarum Competition Model
Awad et al. (2019b) proposed a novel model to imitate the complex patterns observed in Physarum polycephalum generated in competition settings [16]. This new model is based on hexagonal Cellular Automata (CA) and Reaction-Diffusion (RD) systems. This is the first time Physarum has been simulated in a 2-D hexagonal grid that is more applicable to Physarum natural diffusion in a circular pattern to equidistant cells. All other models considered either Von-Neumann (4 adjacent neighbours) [75] or Moore neighbourhoods (8 adjacent neighbours) [86]. However, in Von-Neumann model, diagonal diffusion of Physarum can still occur, while in Moore model the neighbourhoods are not equidistant. In this competition model multiple Physarum interact with each other and with their environment, each Physarum has its autonomous behaviour: it compares information on reward determined by food resources'mass and quality, negative effects of competing neighbours according to their mass, and hunger motivation in order to make correct and adaptive decisions. They believe that competition among different Physarum individuals can lead to the emergence of a complex global behaviour, far beyond the capability of individual Physarum. The individual skills of competition are more efficient to achieve an optimal balance between exploration and exploitation and maintain population diversity.

Physarum-Inspired Applications
In this section, we will address the most important question "What Physarum can offer to computing?". Many Physaruminspired algorithms have been developed and proved to have great potential to solve various optimisation problems using simple heuristics. In this context we will not be restricted to graph optimisation problems as previous reviews [101,77,5,33], we will open the horizon and through light to more recent applications. We will address this issue by briefly reviewing some of the existing researches on these Physarum-inspired applications.

Physarum-Inspired Algorithms for Graph-Optimisation Problems
Physarum protoplasmic flux is changing continuously with the change of environment in its foraging process. This characteristic allows Physarum to have great potentials in dealing with graph-optimisation problems which are considered the main application. Physarum network design has attracted the attention of many researchers as it demonstrated excellent performance in network construction without central consciousness during the process of foraging. The Physarum solver is based on positive feedback where the tubes that are more suitable for transporting the nutrients will grow bigger and will be of less resistance, while the tubes which do not transport enough nutrients will vanish and disappear. This feedback mechanism helps to maximise the number of nutrient sources and to minimise transportation costs [58,95]. The Physarum solver constructs networks by making some nodes in the network "sources" and cytoplasmic streaming to others "sinks". So there is a great difference between the way that Physarum solves the shortest path problem and the traditional methods, including the Dijkstra algorithm [24].
Many mathematical models were proposed to simulate the intelligent behaviour of Physarum (as discussed in Section 8).
The algorithms based on these models were able to find the shortest path in directed and undirected networks. Nakagaki et al. (2000) were the first to show how this simple organism has the ability to find the shortest path between two points in a labyrinth [57]. Subsequent research has confirmed and broadened the range of its computation abilities to spatial representations of various graph problems [101]. It showed that the Physarum's network geometry met the requirements of a smart network: short tubes, close connections among all the branches, and tolerance to dynamic changes. Tero et al. (2010) designed a Physarum bio-inspired networks similar to the Tokyo rail system [82]. The resulting networks are both efficient and robust.
A lot of Physarum-inspired algorithms (PAs) have been proposed to solve challenging network optimisation problems, such as the travelling salesman problem [52] and the Steiner tree problems [46,56], transport network design and simulation [6,87], spanning tree approximation [3], and vehicle routing problems [50]. Recent examples of the Physarum application include: designing supply chain networks [100], community detection [32], and discrete multiobjective optimisation problems [17]. For a detailed discussion on the existing methods and applications refer to [101,77].
These popular Physarum-inspired Algorithms (PAs) have proven its potential in solving challenging network optimisation problems [64,101]. However, some network optimisation problems remain unsolved. New techniques are required to address the large scale of the next-generation networks, where centralised control of communication becomes impractical. Physarum distributed intelligence may inform the design of an adaptive, robust and spatial infrastructure networks with decentralised control systems [77]. We have proposed a Physarum competition model [16], where multiple Physarum with autonomous behaviours react to each other and with their environment without central control to achieve efficient exploration of the whole system evolving to an optimal global network, this has allowed us to deal with the increasingly proposed networks scenarios with multiple sources and multiple sinks. In our previous work, we have presented a Physarum-inspired competition algorithms for mobile wireless sensor networks, where multiple Physarum (as represented by sensors) will sense the surrounding environment, and compete over multiple food resources (as represented by interest points). These algorithms have demonstrated their promising performance in solving node deployment [14] and connectivity restoration even in harsh environment [15].
These network graph-optimisation problems are typically based on the following four strategies: • One source node and one sink node: It was first proposed by Nakagaki [101]. • Multiple source nodes and one sink node: this strategy is to select one terminal to be the sink node and then select the other terminals to be source nodes. It has been applied by Liu et al. (2015b) to solve the classical Steiner tree problem in graphs [46]. It has also been used to solve the prize-collecting Steiner tree problem and the node-weighted Steiner tree problem [78]. • One source node and multiple sink nodes: this strategy is to select one terminal to be the source node and then select the other terminals to be sink nodes. It was first used by Watanabe and Takamatsu (2014) to design transportation networks with fluctuating traffic distributions [94]. • Multiple source nodes and multiple sink nodes: this strategy is to select multiple terminals to be the source nodes and multiple terminals to be the sink nodes. It was recently proposed by Zhang et al. (2016b) to solve the supply chain network design problem [101].

Evolutionary Algorithm Optimisation (Hybrid Models)
Prior knowledge plays a vital role in the computational efficiency of evolutionary algorithms (e.g., Genetic Algorithm, and Ant Colony). Taking advantage of Physarum powerful computational capabilities, such as morphological diversity [34] and positive feedback loop [80], these characteristics have been used to optimise some evolutionary algorithms to improve its efficiency and robustness [102,32].
Ant colony optimisation (ACO) algorithms have been shown to provide an approximate solution for NP-hard problems existing in many real-world applications. However, premature convergence has significantly reduced the performance of these algorithms. Zhang et al. (2014) proposed an optimisation strategy for updating the pheromone matrix in ant colony algorithms based on a Physarum mathematical model [102]. This strategy has accelerated the positive feedback process in ACO, for solving NP-hard problems such as travelling salesman problem (TSP) and 0/1 knapsack problem, which contributed to the quick convergence of the optimal solution [48]. Later on Gao et al. (2018) has incorporated Physarum-inspired initialisation to optimise the genetic algorithm, ant colony optimisation algorithm and Markov clustering algorithm for solving community detection problems [32].

Biological Computing and Physarum Logic Gates
Boolean logic which describes binary arithmetic is fundamental to computer science as electronic logic gates form the basis of digital operations in computers. Organism based Bio-Logic gates have been attempted using cell constituent (bacteria) as transducers [93]. Bacteria have many drawbacks, mainly due to the fragility, short life, limited temperature, and pH conditions. Also, bacteria will often not grow on specific substrates which would be ideal for the cell-transducer interface. Yeast and wild fungi are offering the advantage of high growth rate and the ability to grow on a broad range of surface substrates used for cell-transducer interface [18]. Moreover, yeast can survive for over a long time after dehydration and could be re-hydrated when required.
Like other fungi and yeast, Physarum is accessible to culture on moist filter paper or agar and resist dehydration for a long time. This is why it can be considered as a prospective experimental prototype of biological computers which does not require sophisticated support. In standard electric devices, we deal with electrical signals to code information. However, in a Physarum biological device instead of electrical signals, the calculation process is performed by using the Physarum chemotaxis to food [5,91].
Physarum as a method of biological computing has been extensively studied in the PhyChip project that ran between 2013 and 2016 "Physarum chip: growing computers from slime mould" [9]. A Physarum chip is formed of a living network of protoplasmic tubes that acts as an active non-linear transducer of information, while templates of tubes coated with conductor act as fast information channels. The symbolic-logical, mathematical and programming aspects of the Physarum chip have been studied by Schumann et al. (2015) [71]. Physarum was also used as a Boolean gate, where the presence and absence of Physarum in a given locus of space is equivalent to logic values 1 and 0, respectively [70]. The Physarum chip is expected to solve a wide range of computation tasks, including graph optimisation, logic and arithmetical computing [13].
The EU-funded PhySense project "Physarum Sensor: Biosensor for Citizen Scientists" is an extension of the PhyChip project. This project showed that Physarum is an ideal biological substrate that could be used as a biosensor that converts a biological response into an electrical signal, providing a unique fusion of living and digital technology. The PhySense software calculates any changes in the frequency and amplitude of oscillations in the tubular structures of Physarum. The aim of this project is developing marketable low-cost biosensors for various applications, including environmental monitoring and health [22] 1 .

Conclusion
By studying Physarum foraging behaviour and translating that behaviour into mathematical models, we increase our understanding of how to inspire from biology to develop Physarum bio-inspired algorithms can solve many challenging real world problems. Physarum polycephalum is an example of plasmodial slime moulds. The primitive intelligence of Physarum polycephalum is mostly demonstrated during its plasmodium stage (a large multi-nucleated single cell). that consists of a single cell amoeba-like organism. Physarum senses gradients of chemo-attractants and repellents and forms a yellowish vascular network in search of nutrition. A stimulus triggers the release of a signalling molecule cyclic adenosine monophosphate (cAMP) which starts cytoplasmic streaming. This generates a feedback loop; the higher the rate of cytoplasmic streaming is, the thicker the vein becomes. The Physarum foraging behaviour consists of two simultaneous self-organised processes of expansion (exploration) and shrinkage (exploitation). Just like social insects and animals, Physarum too exhibits swarm intelligence; it shares many features of collective behaviour such as synchronisation, communication, positive feedback, leadership, and response thresholds. There is increasing evidence that a simple organism like Physarum has complex social behaviours including cooperation and competition. Physarum is capable of making complex foraging decisions based on trade-offs between risks, hunger level and food patch quality. The skills of individual competitors are effective methods for inspiration to develop intelligent systems and to provide solutions for decision-making problems.
Physarum may not have brains, but the advantages of Physarum unconventional computational capabilities, as morphological diversity and positive feedback loop, have great potentials for solving many NP-hard problems. Physarum, as a simple organism, has the ability to find the minimum-length between two points in solving the maze problem and discover the shortest path in real-world networks such as the Tokyo railway network using simple heuristics. Much research has confirmed and broadened the range of its computation abilities to spatial representations of various graph optimisation problems. Physarum-inspired initialisation of other bio-inspired techniques has the ability to accelerate convergence and improve the searching capability of evolutionary algorithms (e.g., Genetic Algorithm, and Ant Colony) in terms of accuracy and computational cost. Physarum as a biological model has been studied in the PhyChip and PhySense projects to develop marketable and low-cost biosensors for various applications including environmental monitoring and health.Physarum can be considered one of the biological models of unconventional computation capable of making a programmable Physarum machine.


ActiveAnno: General-Purpose Document-Level Annotation Tool with Active Learning Integration

ActiveAnno is an annotation tool focused on document-level annotation tasks developed both for industry and research settings. It is designed to be a general-purpose tool with a wide variety of use cases. It features a modern and responsive web UI for creating annotation projects, conducting annotations, adjudicating disagreements, and analyzing annotation results. ActiveAnno embeds a highly configurable and interactive user interface. The tool also integrates a RESTful API that enables integration into other software systems, including an API for machine learning integration. ActiveAnno is built with extensible design and easy deployment in mind, all to enable users to perform annotation tasks with high efficiency and high-quality annotation results.

Introduction
Lots of tasks in industry and research require the manual annotation of a potentially large number of documents, for example in content analysis research or supervised machine learning. Existing tools, such as WebAnno (Yimam et al., 2013), allow for span-level annotation tasks like NER and POS tagging. As Neves and Ševa (2019) point out in their review of annotation tools, document-level annotation is a feature missing in most existing tools. ACTIVEANNO is a novel tool created to fill this void. It was created based on five central design goals: 1) Creating annotations of high quality in an efficient manner (quality). 2) Support a broad range of use cases without any additional programming effort (configurability). 3) provide a good user experience through a modern, responsive web application to be more attractive than specialized prototypes of annotation software (responsiveness). 4) Publicly available to extend for future use cases (open source). 5) Provide APIs for easy integration into existing software systems and easy deployment to minimize the upfront effort for using ACTIVEANNO (extensibility). Through this approach, we would like to put forward ACTIVEANNO as a candidate for the default option for document-level annotation in industry and research.

Related Work
Neves and Ševa (2019) conducted an extensive review of 78 annotation tools in total, comparing 15 which met their minimum criteria. Five of those tools support document-level annotations: MAT, MyMiner, tagtog, prodigy, and LightTag. MAT 1 (Bayer, 2015) is designed for what they call the "tag-a-little, learn-a-little (TALLAL) loop" to incrementally build up an annotation corpus, but it is only a research prototype and is not ready to be used in production. MyMiner (Salgado et al., 2012) is an online-only tool without a login or user system. Its main purpose is to classify scientific documents in a biomedical context, which is limited in scope and configuration options and not suitable as a general-purpose tool. The tools tagtog 2 (Cejuela et al., 2014), prodigy 3 , and LightTag 4 are all feature-rich and support some form of machine learning integration, but are commercial with either no free version or a free version with limited functionality. This makes these tools less accessible for projects with limited monetary resources.
According to Neves and Ševa (2019), WebAnno is the best tool fitting their criteria, however, it does not support document-level annotations. WebAnno is a notable example of an annotation tool which is open-source, widely used and featurerich. We adapt some of the functionalities into our ACTIVEANNO document-level annotation tool.
Another annotation tool with limited support for document-level annotations is Doccano 5 (Nakayama et al., 2018), though it is not mentioned in the evaluation of Neves and Ševa. The opensource tool currently supports three distinct annotation tasks: text classification, sequence labeling, and sequence to sequence tasks.
3 Architecture of ACTIVEANNO ACTIVEANNO is a client-server application as depicted in Figure 1. On the server-side, the main component is a backend service written in Kotlin using the Ktor framework. The backend service is stateless, allowing for horizontal scaling for advanced performance requirements. It is connected to a MongoDB database that is used to store documents and annotation projects. There is also a minimal authentication service written in Python and Django, which provides a simple user management UI and the authentication mechanism of JSON web token (JWT) that is used by the frontend and backend components. The authentication part is extracted into this service such that it can be exchanged for an existing or a more sophisticated user management service, if needed. Finally, the frontend is written in Javascript using React, which is served by an Nginx. All backend components are deployed as Docker containers through existing Docker Compose files. The communication between the client and server is done through HTTP requests via the JSON format. ACTIVEANNO documents: A document is represented as a JSON object with a textual field con-taining the document text, for example the text of a tweet or the abstract of a paper. It can optionally have additional fields with meta data that can also be displayed to support the annotation process. Metadata examples include the date and username for tweets, the authors and publication for papers, or the number of stars for an app review. Documents are imported through the UI or API in the JSON format and can be annotated for multiple annotation projects afterward. Annotation definitions: Annotation projects define an annotation task for one or more annotation definitions. An annotation definition describes the required type and form of the annotation that should be created. The typical example is a tag set annotation, where a document is annotated with one or more predefined tags such as spam/no spam, the sentiment or the topic classification of a text. ACTIVEANNO also supports boolean, number, and text annotations with various configuration options such as minimum/maximum values. Annotations and annotation results: For an annotation project, every document can be annotated for every annotation definition of the annotation project, resulting in one annotation per definition. Together, all annotations for a document from a single annotator form an annotation result. Every annotation of the annotation result has a different value structure depending on the type of annotation definition. Additionally, every annotation value can have an associated probability used in the context of automatically generated annotations through the machine learning integration. Annotation process: ACTIVEANNO has a twostep annotation process. In the first step, annotation results are created. They can be created either by annotators, annotation generators (see Section 4), or they can be imported through the import annotation API (see Section 3.2). After every new annotation result, a finalization policy logic is applied to the document and its annotation results. This logic decides if the annotation process is finished for the document and a final annotation result exists. The logic is dependent on the project configuration. The manager of a project can set the number of annotators per document. This is the minimum number of different annotators required for each document until any additional logic is applied. For example, if the number of annotators is set to three, every document will be shown to the annotators until the document is annotated by three users. One annotator can only annotate every document once. After three annotation results were created, the finalization policy is applied. Depending on the selected policy, the annotation results will either be exported individually, or the annotations are merged based on a majority calculation. If no majority is observed, the document can either be presented to an additional annotator until a majority is reached, or to a curator to decide on the correct annotation result. It is also possible to always require a curator for use cases with very high-quality requirements.

Web UI
ACTIVEANNO is a modern single-page and responsive web application. It is fully localized, currently supporting English and German. By using a persistent web database, the application state and therefore the created annotations are automatically persisted. A configurable role system allows for the proper authorization of endpoints. The two main roles are user and manager. A user can be an annotator or curator, a manager has the ability to edit projects as well as analyze the results. There are also the roles producer and consumer to allow the protection of the API of ACTIVEANNO. Producers are allowed to push data into ACTIVEANNO while consumers are allowed to read the annotation results through the export API. Though slightly modified, the user roles were inspired by WebAnno's user management.
The web interface is composed of the login page, a landing page and pages for annotation, curation, and management. On the landing page, users can see their areas of responsibility and switch the application language. The manage page is for users with the manager role, allowing them to create and edit projects, annotation definitions, annotation generators, and the analysis of annotation results.
Figure 2 (left) shows the UI (Mobile version) for editing the basic properties of an example project, like name and description. Besides, the other parts of the manage project component allow configuring the filter condition to query documents from the database, defining which documents are relevant for the project, as well as the field and order of how to sort documents when querying the database. Both the filter and sort inputs translate to MongoDB queries. Additionally, the manager of the project can configure the annotation schema, which is composed of the annotation definitions for the project. From this and the document mapping step, where the manager defines which part (as JSON keys) of the imported documents are relevant for the project, the layout for the annotation task gets generated. The generated layout shows all the metadata, the document text, and the annotation definitions with default input types. Figure 2 (right) shows an example layout for the annotation view (Mobile version). Lastly, the manager can configure how annotation results are able to be exported: either through the REST API, webhooks, or both (see Section 3.2 for the details of the API). Figure 3 shows the annotation UI for a more complex annotation task, in this case on a desktop layout, with six annotation definitions of different types, including Yes/No annotations, single and multi-select tag set annotations (some displayed as buttons, some as drop-down inputs), a number annotation visualized as a slider, an extensible tag input (where annotators select tags created by other annotators or create their own), and an open text input. After a manager created a project and documents are imported into ACTIVEANNO, the annotators can annotate the documents according to the project set up in the annotate subarea. Depending on how the project is set up, the annotated documents might be checked and possibly overwritten by a curator in the curation subarea. In the curation UI, curators can see all previously created annotation results. Curators have the authority to decide if an annotation created by annotators is correct, to provide a final verdict.
After annotation results are finalized, they can be analyzed by the project managers. In addition to accuracy, the inter-annotator agreement (simple agreement with exact matching), as well as the annotation duration is generated as charts in the UI. There is also a table of individual documents, showing the correctness of every annotator and The UI has filter inputs to restrict analyzed annotation results by annotator, date range, or more fine-grained filters.

Import and Export API
ACTIVEANNO provides multiple API endpoints to enable automated document processing and integration into larger software systems. The import document endpoint allows uploading any JSON document or an array of JSON documents. Documents will be assigned a unique ID, stored in the MongoDB, and the IDs will be returned to the caller, so they can be used for future reference, e.g. to export from ACTIVEANNO. The ID is also used to import externally created annotations into ACTIVEANNO for a specific project and document. Imported annotations can be treated like any other created annotation in the agreement process, or as pre-annotations for human annotators.
Through a single export endpoint, annotation results can be exported into other applications for further processing. Through the GET parameters, it can be filtered which annotation results will be exported, for example, based on the timestamp or document IDs. As an alternative to the export API, every project can define a list of webhook URLs, which will be called once a document is finalized.

Annotation Generator
The integration of machine learning and the ability to automate parts of the annotation process are important to increase the efficiency of the annotation process. The basis for automation is the ability to automatically generate annotations without a human annotator. To generalize the concept and to allow for other ways to automatically create annotations, ACTIVEANNO defines the concept of annotation generators. An annotation generator is anything capable of creating an annotation for a specific annotation definition given a document and potentially other previously generated annotations for other annotation definitions. An annotation generator is defined through an abstract class with a generateAnnotation method that every generator needs to implement. Every annotation generator also has to define what is the input to use for the actual annotation generation. It can be any field from the original document, or it can be any value from another created annotation that is part of the same annotation schema, allowing for chaining or conditional connecting of annotation generators.
Currently, ACTIVEANNO has three inbuilt annotation generator implementations. The first one automatically detects the language of the generator input using the language detection library Lingua 6 . This is an example of a statistical and rule-based annotation generator as compared to a machine learning-based generator. The second annotation generator allows calling an external machine learning service through a URL for tag set annotation definitions, which will take the response and map it into the tag set options from the annotation definition. This can be used when an already trained machine learning model exists. The model would have to be wrapped by an HTTP API to comply with the API definition of ACTIVEANNO for this annotation generator. The API is structured to allow for multiple documents to be predicted at once. The third annotation generator is similar to the second one, but also supports automatically updating the external machine learning model by sending an HTTP request with the training data in the body. To support this functionality, the concept of an updatable annotation generator exists. This kind of generator extends the base annotation generator, but also requires its subclasses to implement an update method, where the training data will be aggregated and used to train or update the annotation generator. For this, updatable annotation generators also need to define a threshold when to start the training and when to update an existing model. For example, the first model should be trained after 100 training samples are generated, and then it should be updated for every 25 new training samples. An updatable annotation generator is versioned with a version number and an update state, to ensure the version is actually usable to generate new annotations.
Annotation generators can be triggered to generate/re-generate annotations for a project when appropriate, and they can be triggered to update themselves if they are updatable annotation generators and enough new training data is created to allow for a model update.

Machine Learning Integration
Once the annotation definitions and annotation generators are created and an external machine learning service is provided in compliance with the API of ACTIVEANNO, the last step is to integrate the machine learning module into ACTIVEANNO. For this, a project has multiple configuration possibilities. The first one is the handling policy of generated annotation results. This policy can be set to use the generated annotations as pre-annotations for the annotators. In this case, the annotations will fill out or select the inputs in the annotation panel, giving the annotators the option to just accept the automatically generated annotations, which can reduce the annotation effort. Alternatively, it is possible to set the generator results to be treated equally to an annotator where the results will be included in the finalization logic.
The other important configuration is the sorting policy. With regards to generated annotations, it is possible to overwrite the normal sorting order of the project. This can be set to prefer documents with existing generated annotation results. In this case, if only a subset of documents has received their generated annotations at a point in time, they will be preferred in sending them to the annotators. This means that if pre-annotations are available, they will always be shown before documents without pre-annotations. The second option is to set the sorting to active learning with uncertainty sampling. This is used to support active learning, where the documents with the lowest confidence values associated with the generated annotations will be preferred (see Section 4.2). We also have an alternative approach for machine learning integration that relies on the import annotation API. Imported annotations can be used instead of internally generated annotations. For updating a machine learning model, the REST API or webhook support can be used to get the final annotation results. In this case, all the logic regarding how to extract the data and when to update the model need to be implemented externally. This approach might be more useful if the required logic or process is vastly different from the inbuilt annotation generator concept.

Active Learning Process
When there is no existing training data for an annotation definition, ACTIVEANNO can be used to build up a training dataset based on active learning with uncertainty sampling. The training data can either be imported once at the start of the active learning process or continuously, for example, if the data comes from a news crawler or the Twitter API. The active learning process would work as follows: First, when there is no training data, documents get manually labeled by an annotator. If a threshold of the annotation generator is reached, triggering the update of the generator will result in the training data being aggregated and sent to the external service. Triggering the generate annotations functionality (from the UI or via an API) will result in the newly trained generator model that will create predictions for all remaining documents in the project. Afterwards, when the projects sorting policy is set to active learning, the confidence values from the newly generated annotations will be used to sort the documents for annotation, those with the lowest confidence being presented first.
This process can then be repeated until the machine learning model is performing well enough to be partly or fully automated. This is similar to the "tag-a-little, learn-a-little loop" from MAT (Bayer, 2015). If combined with enabling pre-annotations, it is also very similar to the annotation process of RapTAT (Gobbel et al., 2014). To partly automate the process, the project has to be configured to treat the generator as an annotator and to require one annotator per document. Additionally, the configuration option of the finalize condition has to be set to some confidence threshold, for example, 80%. Then, only the documents with a confidence value below 80% will be required to be annotated further. To fully automate the process, the finalize condition should be set to always to accept the annotations automatically without additional conditions.

Use Cases
ACTIVEANNO is designed to be applicable in many settings, including industry and research; for small projects on a local machine and large projects with many users on the internet; for use cases with and without machine learning components. We have used ACTIVEANNO in two industry setups, to test its suitability to collect real-world annotation requirements. It was directly deployed on the service cluster of a company, configured via environment variables, and connected to the existing system via its API with some small additions to the existing software system to get documents into ACTIVEANNO. For the machine learning integration, a small Python service wrapping fastText (Bojanowski et al., 2017) models was employed. The data for the experiments were around 250,000 Ger-man textual feedback comments obtained from a retail context.
The first experiment was set up to analyze the effects of pre-annotations on annotation quality and efficiency. Three annotation definitions, namely spam/not spam, sentiment, and topic classification were annotated by two annotators employed at the company. One condition was provided without pre-annotations while the other one was provided with pre-annotations for all three annotation definitions. The annotations were created by pre-trained machine learning models that are integrated into ACTIVEANNO through the annotation generator and the machine learning-related APIs. Through the analyze functionality of ACTIVEANNO, the inter-annotator agreement (IAA), annotation duration, and the accuracy of annotators as well as the machine learning models are compared inside the tool. The final result showed a 28% faster annotation without any change of annotation accuracy or annotator agreement for the condition with preannotations. ACTIVEANNO enabled the research project itself while the annotators reported a positive user experience using the tool. They reported that the tool is easy, fast, and convenient to use.
The second experiment explored the incremental and active learning capabilities of ACTIVEANNO.
A new annotation definition about the utility (or information quality) of a comment with three classes (useful, okay, spam) was created as it was a new business requirement to create such annotations for further aggregation and processing. During the experiment, multiple new machine learning models for different conditions were created by annotating new comments inside ACTIVEANNO and triggering the automatic annotation generator updating and re-annotating functionality. By additionally enabling pre-annotations, annotators had reduced effort for selecting the correct annotation option, once the model had an acceptable level of accuracy. Selecting the best performing model based on the experiment conditions then enables and improves the regular annotation process of the company. Once the model performs well enough while being used for pre-annotation, it could then be used to partly automate the process as described by simply editing the project configuration.
Finally, as both experiments were conducted on non-publicly available data, we created another example project based on the OffensEval 2019 shared task (Zampieri et al., 2019), specifically sub-task A. The task is directly integrated as an example project in ACTIVEANNO, including a machine learning component that can be updated through ACTIVEANNO. Please refer to the demo 7 and video 8 to see this use case in action.

Conclusion and Future Work
ACTIVEANNO supports several mechanisms to produce high-quality annotations with an efficient annotation process, like the number of annotators per document, a configurable agreement logic, curators, machine learning integration through annotation generators, pre-annotations, treating annotation generators as annotators, partly or fully automating annotations, and updating annotation generators with incremental or active learning. A fully configurable annotation schema with annotation definition types like tag sets, numbers and texts, a modern and responsive web UI, as well as flexible user management allows ACTIVEANNO to be adaptable to many different kinds of annotation process requirements. The RESTful API and webhooks allow for easy integration with other software components.
Future work planned is to add in-app feedback between curators and annotators for improving annotator performance, adding more in-built annotation generators for other types of annotation definitions, UI improvements (layout editor, better display of very long documents) and span-level annotations as well as hybrid-level annotations which can be defined either on a span or document level.
Most importantly, ACTIVEANNO was designed with extensibility and flexibility in mind. It is available as open-source software under the MIT license.