Clustering Routing Optimization Method Based on Adaptive Evolutionary Algorithm for Wireless Sensor Network

Abstract

The present invention discloses a clustering routing optimization method based on adaptive evolutionary algorithm for a wireless sensor network, comprising following steps: performing population initialization by initial position and energy information of sensor nodes; calculating fitness values, and implementing iterative operation of elite preservation, adaptive crossover and mutation; after the iteration, selecting a cluster head; routing data packet of the cluster head to a base station. Convergence process of the evolutionary algorithm is improved by nonlinearly adjusting the probability of crossover and mutation; upper and lower bound of crossover and mutation operators are dynamically adjusted by fitness value; adding an incentive factor, adjusting the crossover and mutation probability when the fitness value tends to converge, and running the algorithm again to confirm that a new optimal value is generated. The global search capability and convergence speed of the algorithm are improved by the above method, and avoiding local convergence.

Claims

1. A clustering routing optimization method based on adaptive evolutionary algorithm for a wireless sensor network, comprising the following steps: Step 1, deploying a multitude of sensor nodes randomly in a monitoring area, establishing a network energy consumption model, acquiring a distance between each pair of the multitude of sensor nodes according to a received signal strength; performing population initialization according to a multitude of initial positions and energy information of the multitude of the sensor nodes, setting q as a number of iteration, with an initial value of q=0; setting q.sub.max as a maximum number of iteration, and q.sub.max being a positive integer greater than 30: denoting a size of a population as m, an x-th individual in the population as C(x), assigning a length of each individual to be a number of the multitude of sensor nodes n, thus obtaining a population set as $\mathrm{Pop}=\underset{x=1}{\overset{m}{.Math.}}C\left(x\right),$ a set of individuals as C(x)={B.sub.1,B.sub.2,B.sub.3, . . . B.sub.i . . . B.sub.n}, wherein B.sub.i denoting a value of a gene on an i-th individual, B.sub.i being determined by energy of node S.sub.i, an average energy of surviving nodes in the network and a threshold T(s), wherein T(s) being shown as: $T\left(s\right)=\{\begin{array}{cc}\frac{p}{1-p\times \left[r\mathrm{mod}\left(1/p\right)\right]}& \mathrm{if}s\in G\\ 0& \mathrm{otherwise}\end{array};$ wherein, p being a ratio of a number of cluster heads to a total number of nodes, p=0.05, r being a number of current rounds, and G being a set of nodes failing to become a cluster head in previous 1/p rounds; randomly generating a 0˜1 random number for each node and comparing it with a threshold T(s); defining: $C\left(x,i\right)=B_i=\{\begin{array}{cc}1& S_i.E\ge E_{\mathrm{avgAlive}},\mathrm{rand}\le T\left(s\right)\\ 0& 0\le S_i.E<E_{\mathrm{avgAlive}}\\ -1& S_i.E<0\end{array},$ wherein S.sub.i.Math.E representing a remaining energy of node S.sub.i, E.sub.avgAlive denoting an average energy of surviving nodes in the network; Step 2, constructing a fitness function of the evolutionary algorithm for the x-th individual based on average energy of nodes, average energy of next-hop nodes, average node degree of next-hop nodes, sum of distances from each cluster head node to a base station and sum of distances from each member node to a corresponding cluster head as: $f\left(x\right)=\frac{E_{\mathrm{avg}}+E_{\mathrm{next}-\mathrm{avg}}+D_{\mathrm{deg}\mathrm{reen}}}{E_{\mathrm{sum}}},$ $E_{\mathrm{sum}}=e^{E_{\mathrm{sum}1}+E_{\mathrm{sum}2}},$ $E_{\mathrm{sum}1}=\frac{{\mathrm{sumD}}_{\mathrm{CH}.fwdarw.\mathrm{BS}}\left(x\right)-{\mathrm{minpopD}}_{\mathrm{CH}.fwdarw.\mathrm{BS}}+1}{1+{\mathrm{avgpopD}}_{\mathrm{CH}.fwdarw.\mathrm{BS}}},$ $E_{\mathrm{sum}2}=\frac{{\mathrm{sumD}}_{S.fwdarw.\mathrm{CH}}\left(x\right)-{\mathrm{minpopD}}_{S.fwdarw.\mathrm{CH}}+1}{1+{\mathrm{avgpopD}}_{S.fwdarw.\mathrm{CH}}},$ wherein, E.sub.avg denoting the average energy of the node, E.sub.next-avg representing the average energy of the next-hop node, D.sub.degreen being the average node degree of next-hop node, sumD.sub.CH.fwdarw.BS (x) representing the sum of the distances from said each cluster head node to the base station, and sumD.sub.S.fwdarw.CH (x) denoting the sum of the distances from said each member node to the corresponding cluster head, minpopD.sub.CH.fwdarw.BS denoting a minimum value of the sum of the distances from each cluster head nodes to the base station for all individuals in the population, minpopD.sub.S.fwdarw.CH representing a minimum value of the sum of the distances from the member nodes of all individuals in the population to the corresponding cluster head, avgpopD.sub.CH.fwdarw.BS denoting an average of the sum of the distances from said each cluster head node to the base station for all individuals in the population, avgpopD.sub.S.fwdarw.CH representing an average of the sum of the distances from the member nodes to the corresponding cluster head for all individuals in the population; Step 3, constructing an adaptive crossover probability formula as: $P_c\left(x\right)=P_{c2}+\frac{P_{c1}-P_{c2}}{1+P_e},$ $P_e=e^{10.Math.\frac{f\left(x\right)-f_{\mathrm{avg}}}{f_{\max }-f_{\mathrm{avg}}}},$ wherein P.sub.c1 and P.sub.c2 being upper and lower bound of crossover probability adaptive adjustment, respectively; upper bound being: P.sub.c1=F.sub.1(f′(x))=P.sub.c−Δf′(x)*(−0.1), P.sub.c2<P.sub.c1≤0.97, when P.sub.c1 being greater than 0.97, upper bound of crossover probability being set to 0.97, Δf′(x) being a variation trend of the fitness value f(x), and the lower bound P.sub.c2=0.1, f.sub.max being a maximum value of individuals fitness value in the population, f.sub.avg being an average value of individuals fitness value in the population; Step 4, constructing an adaptive mutation probability formula as: $P_m\left(x\right)=P_{m2}+\frac{P_{m1}-P_{m2}}{1+P_e},P_e=e^{10.Math.\frac{f\left(x\right)-f_{\mathrm{avg}}}{f_{\max }-f_{\mathrm{avg}}}},$ wherein P.sub.m1 and P.sub.m2 being upper and lower bound of mutation probability adjustment, respectively; the upper bound being: P.sub.m1=F.sub.2(f′(x))=P.sub.m−Δf′(x)*(−0.01), and lower bound P.sub.m2, =0.01, p.sub.m2<p.sub.m1≤0.1, when the P.sub.m1 being greater than 0.1, the upper bound of mutation probability being set to 0.1, Δf′(x) being the variation trend of the fitness value f(x), f.sub.max being the maximum value of individuals fitness value in the population, f.sub.avg being the average value of individuals fitness value in the population; Step 5, constructing a selection rule: while preserving the individual H with the highest fitness value in the current population, letting individual H continue to participate in crossover and mutation operations, and if a worst-performing individual L in the next generation having a smaller fitness value than individual H in the previous generation, replacing individual L directly with individual H, defining two sets as: $\{\begin{array}{c}\begin{array}{c}{C}_{\max }=\{C_{\max }\left(k\right):f\left[C_{\max }\left(k\right)\right]=\\ \max \left[f\left(C\left(k\right)\right)\right]|C_{\max }\left(f\right)\in \mathrm{Pop}\left(k\right),k=1,2,.Math.\}\end{array}\\ \begin{array}{c}{C}_{\min }=\{C_{\min }\left(k\right):f\left[C_{\min }\left(k\right)\right]=\\ \min \left[f\left(C\left(k\right)\right)\right]|C_{\min }\left(f\right)\in \mathrm{Pop}\left(k\right),k=1,2,.Math.\}\end{array}\end{array},$ wherein C.sub.max(k) and C.sub.min(k) representing an optimal and an inferior individuals in the k-th generation population Pop(k), respectively, f[C.sub.max(k)] and f[C.sub.min(k)] being the fitness value of the corresponding individual, if f[C.sub.max(k)]>f[C.sub.min(k+1)], then C.sub.min(k+1)=C.sub.max(k), f[C.sub.min (k+1)]=f[C.sub.max (k)]; Step 6, calculating the fitness value according to the fitness function in Step 2, setting q=q+1; performing selection, adaptive crossover and mutation operations based on the fitness value to generate new populations; with each point on the individual having a chance of crossover and mutation, upper and lower bounds of the crossover and mutation operators being adjusted with a trend of the fitness values, and probabilities of crossover and mutation being adjusted nonlinearly with the size of the individual fitness values; most individuals in the population that being smaller than the average performing crossover and mutation with a high probability, and a multitude of excellent individuals larger than the average performing crossover and mutation with a lower probability; Step 7, activating a perturbation incentive factor δ.sub.T to avoid local convergence at convergence of the fitness value, the convergence denoting that a change rate of fitness value obtained by continuously calculating the fitness value function for 5 times being less than 0.01 after Step 6, T being the moment when the algorithm tends to converge, adjusting the crossover probability P.sub.c to 0.5 and the mutation probability P.sub.m to 0.05, and proceeding to Step 6, calculating the fitness value, if no larger fitness value being generated, it being considered that the algorithm is currently converging to the optimal state, proceeding to step 9; if a better fitness value being produced, continuing to perform step 8; Step 8, determining whether q reaches the iteration stopping condition that a number of iterations is no less than the maximum fitness value q.sub.max, if q<q.sub.max, proceeding to step 6; if q=q.sub.max, proceeding to step 9; Step 9, clustering a multitude of network nodes according to the clustering scheme in the population individuals, determining whether the cluster head is within the communication range of the base station, if yes, the cluster head communicating directly with the base station; otherwise, selecting the cluster head node as the relay node that is closer to the base station than the current cluster head, routing the data packet to the relay node until the packet is delivered to the base station.

2. The adaptive evolutionary algorithm-based clustering routing method for WSNs of claim 1, wherein q.sub.max is between 500 and 600.

3. (canceled)

4. (canceled)

5. (canceled)

6. (canceled)

7. (canceled)

Description

DESCRIPTION OF FIGURES

[0024] FIG. 1 is a schematic diagram showing the adaptive evolutionary algorithm-based clustering routing optimization method for WSNs of the present disclosure;

[0025] FIG. 2 is a flow chart showing the adaptive evolutionary algorithm-based clustering routing optimization method for WSNs of the present disclosure;

[0026] FIG. 3 is a schematic diagram showing the adaptive crossover operation module of the present embodiment;

[0027] FIG. 4 is a schematic diagram showing the adaptive mutation operation module of the present embodiment;

[0028] FIG. 5 is a schematic diagram showing the adaptive crossover operator curve of the present embodiment;

[0029] FIG. 6 is a schematic diagram showing the adaptive mutation operator curve of the present embodiment;

[0030] FIG. 7 is a realistic simulation diagram showing the adaptive crossover probability changing with the fitness value of the present embodiment;

[0031] FIG. 8 is a realistic simulation diagram showing the adaptive mutation probability changing with the fitness value of the present embodiment;

EMBODIMENTS

[0032] The clustering routing optimization method of WSNs based on adaptive evolutionary algorithm proposed by the disclosure is further described in detail below in combination with the attached drawings and specific embodiments. According to the following description and claims, the advantages and features of the disclosure will be clearer. It should be noted that the drawings adopt a very simplified form and employ imprecise ratios, which are only used to facilitate and clearly illustrate the purpose of the embodiment.

[0033] The core idea of the present disclosure: The present disclosure provides a clustering routing optimization method of WSNs based on adaptive evolutionary algorithm, which adjusts the upper and lower bounds of the crossover and mutation operator, and improves the selection, crossover and mutation mechanism of evolutionary algorithm. In the initial convergence, the activation of the incentive factor can increase the opportunity of attempts, improving the global search ability and convergence speed of the algorithm, and avoiding falling into local optimum, solving the problem of poor real-time performance of clustering by employing intelligent optimization algorithms. In the clustering process, the cluster heads are selected by considering five factors: the distance between each node and cluster head node, the distance between cluster head node and sink node, the remaining energy of each node, the average energy of next-hop node and the node degree of next-hop node. The cluster head node calculates the distance between neighboring cluster heads and communicates with the base station by multi-hop according to the result, improving the network lifetime and data transmission efficiency.

[0034] FIG. 1 is a schematic diagram showing the adaptive evolutionary algorithm-based clustering routing optimization method for WSNs of the present disclosure. As shown in FIG. 1, the network structure of a clustering routing optimization method for WSNs based on the adaptive evolutionary algorithm includes a number of cluster type structures 11 and base station 12. Each cluster type structures 11 contains a cluster head node 111 and a number of common nodes 112. The sensor nodes collect data information from the surrounding environment and transmit the collected data to the base station 12 by multi-hop for further analysis and processing.

[0035] FIG. 2 is a flow chart showing the adaptive evolutionary algorithm-based clustering routing optimization method for WSNs of the present disclosure. As shown in FIG. 2, the clustering routing optimization method based on the adaptive evolutionary algorithm for WSNs, and comprises the following steps:

[0036] Step 1, deploying a multitude of sensor nodes randomly in a monitoring area, establishing a network energy consumption model, acquiring a distance between each pair of the multitude of sensor nodes according to a received signal strength.

[0037] Step 2, performing population initialization according to a multitude of initial positions and energy information of the multitude of the sensor nodes, setting q as a number of iteration, with an initial value of q=0; setting q.sub.max as a maximum number of iteration, and q.sub.max being a positive integer greater than 30.

[0038] Step 3: calculating the fitness value according to the fitness function in Step 2, q=q+1; performing elite preservation, adaptive crossover and mutation operations based on fitness values to generate new populations, each point on an individual has a chance of crossover and mutation, the upper and lower bounds of the crossover and mutation operators are adjusted with the trend of the fitness values, and the probabilities of crossover and mutation are adjusted nonlinearly with the size of the individual fitness values, when the fitness value tends to converge, the incentive factor is activated to avoid local convergence, the convergence denotes that a change rate of fitness value obtained by continuously calculating the fitness value function for 5 times is less than 0.01, adjusting the crossover and mutation probabilities, and calculating the fitness function anew.

[0039] Step 4, determining whether the q reaches the iteration stopping condition that iterations reach the number of settings q.sub.max, if q<q.sub.max, proceeding to step 6; if q=q.sub.max, proceeding to step 3.

[0040] Step 5: determining whether the cluster head is within the communication range of the base station, if yes, the cluster head communicates directly with the base station; otherwise, selecting the cluster head node as the relay node that is closer to the base station than the current cluster head, routing the data packet to the relay node until the packet is delivered to the base station.

[0041] In the step of Step 1, establishing the network energy consumption model, if the node needs to transmit one bit data to the node whose distance from the node is d, the energy consumption of the node is:

[00009]$E_{\mathrm{Tx}}\left(l,d\right)=\{\begin{array}{cc}l\times E_{\mathrm{elec}}+l\times {\epsilon }_{\mathrm{fs}}\times d^2& \mathrm{if}d<d_0\\ l\times E_{\mathrm{elec}}+l\times {\epsilon }_{\mathrm{mp}}\times d^4& \mathrm{if}d\ge d_0\end{array},$

wherein d.sub.0=√{square root over (ε.sub.fs/ε.sub.mp)} denotes the distance threshold, E.sub.eIec represents the energy consumed to transmit or receive one bit data, ε.sub.fs and ε.sub.mp indicate the power amplification factor at different communication distances.

[0042] In the step of Step 2, performing population initialization according to a multitude of initial positions and energy information of the multitude of the sensor nodes, setting a number q as fitness value calculation and counting each time to judge whether the calculation being terminated:

[0043] Denoting a size of a population as m, an x-th individual in the population as C(x), assigning a length of each individual to be a number of the multitude of sensor nodes n, thus obtaining a population set as

[00010]$\mathrm{Pop}=\stackrel{m}{\underset{x=1}{.Math.}}C\left(x\right),$

a set of individuals as C(x)={B.sub.1,B.sub.2,B.sub.3, . . . B.sub.i . . . , B.sub.n}, wherein B.sub.i denoting a value of a gene on an i-th individual, B.sub.i being determined by energy of node S.sub.i, an average energy of surviving nodes in the network and a threshold T(s); wherein T(s) being shown as:

[00011]$T\left(s\right)\{\begin{array}{cc}\frac{p}{1-p\times \left[r\mathrm{mod}\left(1/p\right)\right]}& \mathrm{if}s\in G\\ 0& \mathrm{otherwise}\end{array};$

[0044] wherein, p being a ratio of a number of cluster heads to a total number of nodes, r being a number of current rounds, and G being a set of nodes failing to become a cluster head in previous 1/p rounds, p=0.05, m=20.

[0045] Each node randomly generates a 0˜1 random function and comparing it with a threshold T(s), if it is less than or equal to the T(s) and the energy of node S.sub.i is greater than or equal to the average energy of the surviving nodes in the current network, B=1, selecting the node S.sub.i as the cluster head; when the node energy is greater than 0 but less than the average energy, B.sub.i=0; when the node energy is less than 0, B.sub.i=−1, the discriminant formula for B.sub.i is:

[00012]$C\left(x,i\right)=B_i=\{\begin{array}{cc}1& S_i.E\ge E_{\mathrm{avgAlive}},\mathrm{rand}\le T\left(s\right)\\ 0& 0\le S_i.E<E_{\mathrm{avgAlive}}\\ -1& S_i.E<0\end{array},$

wherein S.sub.i.Math.E represents the remaining energy of node S.sub.i, E.sub.avgAlive denotes the average energy of surviving nodes in the network.

[0046] In the step of Step 3, calculating the fitness values: the x-th individual fitness function in the population is

[00013]$f\left(x\right)=\frac{E_{\mathrm{avg}}+E_{\mathrm{next}-\mathrm{avg}}+D_{\mathrm{degreen}}}{E_{\mathrm{sum}}},E_{\mathrm{sum}}=e^{E_{\mathrm{sum}1}+E_{\mathrm{sum}2}},E_{\mathrm{sum}1}=\frac{{\mathrm{sumD}}_{\mathrm{CH}.fwdarw.\mathrm{BS}}\left(x\right)-{\mathrm{minpopD}}_{\mathrm{CH}.fwdarw.\mathrm{BS}}+1}{1+{\mathrm{avgpopD}}_{\mathrm{CH}.fwdarw.\mathrm{BS}}},E_{\mathrm{sum}2}=\frac{{\mathrm{sumD}}_{S.fwdarw.\mathrm{CH}}\left(x\right)-{\mathrm{minpopD}}_{S.fwdarw.\mathrm{CH}}+1}{1+{\mathrm{avgpopD}}_{S.fwdarw.\mathrm{CH}}},$

wherein E.sub.avg denotes the average energy of the node, E.sub.next, represents the average energy of the next-hop node, D.sub.degreen is the average node degree of next-hop node, sumD.sub.CH.fwdarw.BS (x) represents sum of the distance from each cluster head nodes to the base station, and sumD.sub.S.fwdarw.CH (x) denotes sum of distances from member nodes to the corresponding cluster head, minpopD.sub.CH.fwdarw.BS denotes the minimum value of the sum of the distances from each cluster head nodes to the base station for all individuals in the population, minpopD.sub.S.fwdarw.CH represents the minimum value of the sum of the distances from the member nodes of all individuals in the population to the corresponding cluster head, avgpopD.sub.CH.fwdarw.BS denotes the average of the sum of the distances from each cluster head nodes to the base station for all individuals in the population, avgpop.sub.S.fwdarw.CH represents the average of the sum of the distances from the member nodes to the corresponding cluster head for all individuals in the population.

[0047] Elite preservation: while preserving the individual H with the highest fitness value in the current population, letting individual H continue to participate in crossover and mutation operations, and if the worst-performing individual L in the next generation has a smaller fitness value than individual H in the previous generation, replacing individual L directly with individual H, defining two sets as:

[00014]$\{\begin{array}{c}\begin{array}{c}{C}_{\max }=\{C_{\max }\left(k\right):f\left[C_{\max }\left(k\right)\right]=\\ \max \left[f\left(C\left(k\right)\right)\right]|C_{\max }\left(f\right)\in \mathrm{Pop}\left(k\right),k=1,2,.Math.\}\end{array}\\ \begin{array}{c}{C}_{\min }=\{C_{\min }\left(k\right):f\left[C_{\min }\left(k\right)\right]=\\ \min \left[f\left(C\left(k\right)\right)\right]|C_{\min }\left(f\right)\in \mathrm{Pop}\left(k\right),k=1,2,.Math.\}\end{array}\end{array},$

wherein C.sub.max(k) and C.sub.min(k) representing the optimal and inferior individuals in the k-th generation population Pop(k), respectively, f[C.sub.max(k)] and f[C.sub.min(k)] are the fitness value of the corresponding individual, if f[C.sub.max(k)]>f[C.sub.min(k+1)], then C.sub.min(k+1)=C.sub.max(k), f[C.sub.min (k+1)]=f[C.sub.max (k)].

[0048] In traditional evolutionary algorithms, individuals who perform simply crossover and mutation operation with each other are likely to destroy the better individuals. This does not achieve the purpose of accumulating better genes, but rather destroy the otherwise good genes. In order to prevent the loss of the optimal individual of the current population in the next generation, resulting in the genetic algorithm cannot converge to the global optimal solution, the present embodiment implements the elite preservation strategy. While preserving the individual H with the highest fitness value in the current population, letting individual H continue to participate in crossover and mutation operations, and if the worst-performing individual L in the next generation has a smaller fitness value than individual H in the previous generation, replacing individual L directly with individual H. The elite preservation strategy prevents optimal individuals from being destroyed by crossover and mutation operations.

[0049] FIG. 3 is a schematic diagram showing the adaptive crossover operation module of the present embodiment 1. As shown in FIG. 3, the crossover operation is to interchange and recombine parts of two chromosomes to produce two new individuals. Through crossover recombination, the search ability of the genetic algorithm is greatly improved. The embodiment of the present disclosure adopts the mode of two-point crossover, firstly, a random number C.sub.rand(x) in the range of 0˜1 is randomly generated for individual x in the population. When C.sub.rand(x)≤P.sub.c(x), two gene cut points CP.sub.1 and CP.sub.2 are randomly selected on individual x, exchanging the genes between CP.sub.1 and CP.sub.2 on individual x with the corresponding position of individual x+2.

[0050] FIG. 4 is a schematic diagram showing the adaptive mutation operation module of the present embodiment. As shown in FIG. 4, during the evolutionary process, there may be some errors leading to gene mutation. The mutation operation is based on this phenomenon, setting the mutation probability, some gene values on the chromosome are mutated in order to increase the diversity of the population and avoiding falling into a local optimum. Firstly, a random number M.sub.rand (B.sub.i) in the range 0˜1 is randomly generated for each gene on individual x. When M.sub.rand(B.sub.i)≤P.sub.c (x), replacing the mutated gene value B.sub.i. For node S.sub.i, it becomes 1 when the corresponding B.sub.i=0 and vice versa.

[0051] In traditional evolutionary algorithms, the crossover probability P.sub.c and the mutation probability P.sub.m are usually certain values. If P.sub.c or P.sub.m is too large, the structure of individuals with higher fitness values will be easily destroyed, and the algorithm will fall into random search, losing the meaning of iterative optimization of genetic algorithm. If P.sub.c or P.sub.m is too small, the generation of new individuals in the population will also become difficult, leading to a stagnation of the evolutionary process and falling into local optimum. Therefore, when employing classical genetic algorithm to solve different problems, it is necessary to adjust until the appropriate crossover probability and mutation probability are selected, increasing the workload. In order to address this problem, some researchers have proposed a new adaptive genetic algorithm (NAGA). In order to avoid falling into local optimum, NAGA improves the crossover and mutation operators on the basis of AGA, which is defined as:

[00015]$P_c=\{\begin{array}{c}\frac{P_{c1}\left(f_{\mathrm{avg}}-f^{\prime }\right)+P_{c2}\left(f-f_{\min }\right)}{f_{\mathrm{avg}}-f_{\min }}{f}^{\prime }<f_{\mathrm{avg}}\\ \frac{P_{c2}\left(f_{\mathrm{avg}}-f^{\prime }\right)+P_{c3}\left(f^{\prime }-f_{\min }\right)}{f_{\max }-f_{\mathrm{avg}}}{f}^{\prime }\ge f_{\mathrm{avg}}\end{array}$$P_m=\{\begin{array}{c}\frac{P_{m1}\left(f_{\mathrm{avg}}-f^{\prime }\right)+P_{m2}\left(f-f_{\min }\right)}{f_{avg}-f_{\min }}{f}^{\prime }<f_{\mathrm{avg}}\\ \frac{P_{m2}\left(f_{avg}-f^{\prime }\right)+P_{m3}\left(f^{\prime }-f_{\min }\right)}{f_{\max }-f_{\mathrm{avg}}}{f}^{\prime }\ge f_{\mathrm{avg}}\end{array}$

[0052] wherein, f.sub.max is the maximum fitness value, f.sub.avg is the average fitness value, f.sub.min is the minimum fitness value, f′ is the larger fitness value of the two crossed individuals, and f is the fitness value of the current individual, P.sub.c1>P.sub.c2>P.sub.c3, P.sub.m1>P.sub.m2>P.sub.m3.

[0053] Although NAGA avoids the algorithm from the local optimum in a certain extent, it ignores the number distribution of individuals. If the method in NAGA is adopted, and the crossover and mutation probability can be adjusted linearly with the size of the individual fitness value, a multitude of excellent individual structures in the population may still be destroyed.

[0054] Therefore, P.sub.c and P.sub.m should change slowly and remain at higher levels when individual fitness values are low; P.sub.c and P.sub.m should change equally slowly and remain at higher levels when individual fitness values are high. This operation maintains population diversity while preserving more structures of superior individuals. Crossover and mutation probabilities should be adjusted nonlinearly with the size of individual fitness values. In order to realize this adaptive nonlinear change of crossover and mutation probability, embodiment of the invention adopts sigmoid function to quantify the adaptive adjustment of crossover and mutation probability. The top and bottom of sigmoid function are relatively smooth, which can meet the requirements of this paper on the nonlinear change of crossover and mutation probability.

[0055] The crossover and mutation formula based on sigmoid function provided by embodiment of the invention is as follows:

[0056] Adaptive crossover probability formula is:

[00016]$P_c\left(x\right)=P_{c2}+\frac{P_{c1}-P_{c2}}{1+P_e},P_e=e^{10.Math.\frac{f\left(x\right)-f_{\mathrm{avg}}}{f_{\max }-f_{\mathrm{avg}}}},$

wherein P.sub.c1 and P.sub.c2 are the upper and lower bound of crossover probability adjustment, respectively; the upper bound is: P.sub.c1=F.sub.1(f′(x))=P.sub.c−Δf′(x)*(−0.1), P.sub.c2<P.sub.c1≤0.97, when the P.sub.c1 is greater than 0.97, the upper bound of crossover probability is set to 0.97, Δf′(x) is the variation trend of the fitness value f(x), and the lower bound P.sub.c2=0.1, f.sub.max is the maximum value of individuals fitness value in the population, f.sub.avg is the average value of individuals fitness value in the population.

[0057] Adaptive mutation probability formula is:

[00017]$P_m\left(x\right)=P_{m2}+\frac{P_{m1}-P_{m2}}{1+P_e},P_e=e^{10.Math.\frac{f\left(x\right)-f_{\mathrm{avg}}}{f_{\max }-f_{\mathrm{avg}}}},$

wherein P.sub.m1 and P.sub.m2 are the upper and lower bound of mutation probability adjustment, respectively; the upper bound is: P.sub.m1=F.sub.2 (f′(x))=P.sub.c−Δf′(x)*(−0.01), and the lower bound P.sub.m2=0.01, p.sub.m2<p.sub.m1≤0.1, when the P.sub.m1 is greater than 0.1, the upper bound of mutation probability is set to 0.1, Δf′(x) is the variation trend of the fitness value f(x), f.sub.max is the maximum value of individuals fitness value in the population, f.sub.avg is the average value of individuals fitness value in the population.

[0058] When the change of fitness value tends to be smooth, in order to avoid local optimum, the incentive δ.sub.T is activated, to solve the problem of premature convergence of the algorithm, adjusting the crossover probability P.sub.c to 0.5 and the mutation probability P.sub.m to 0.05, and proceeding to Step 6, calculating the fitness value. If no larger fitness value is generated, it is considered that the algorithm is currently converging to the optimal state; if a better result is produced, the algorithm needs to continue and try to converge again.

[0059] FIG. 5 is a schematic diagram showing the adaptive crossover operator curve of the present embodiment. As shown in FIG. 5, the maximum value of individual fitness in the population, giving a smaller crossover probability to avoid falling into a local optimum, the minimum value of the individual fitness value in the population, giving a larger crossover probability to obtain a satisfactory fitness value.

[0060] FIG. 6 is a schematic diagram showing the adaptive mutation operator curve of the present embodiment. As shown in FIG. 6, for the maximum value of individual fitness in the population, a smaller mutation probability is given to avoid falling into a local optimum, and for the minimum value of the individual fitness value in the population, a larger mutation probability is given to obtain a satisfactory fitness value.

[0061] Most individuals below the average value in the population continue to cross and mutate with high probability, while some excellent individuals above the average value continue to cross and mutate with low probability.

[0062] FIG. 7 is a realistic simulation diagram showing the adaptive crossover probability changing with the fitness value of the present embodiment; FIG. 8 is a realistic simulation diagram showing the adaptive mutation probability changing with the fitness value of the present embodiment. As shown in FIG. 7 and FIG. 8, when most fitness values at a relatively low level, setting their crossover and mutation probabilities higher.

[0063] Further, in the embodiment of the present invention, q.sub.max is between 500 and 600.

[0064] Obviously, it should be noted that the above descriptions are only preferred embodiments of the invention together with the underneath technical principles. A person skilled in the art understands that the invention is not limited to the particular embodiments described herein and that it is possible for a person skilled in the art to make any appreciable variation, readjustment or replacement without departing from the scope of protection of the invention. Therefore, although the present invention is described in more detail through the above embodiments, the present invention is not limited to the above embodiments, but may include many other equivalent embodiments without departing from the conception of the present invention, and the scope of the present invention is determined by the scope of the appended claims.