The Research Of Efficient Swarm Intelligence Algorithms

The optimization problem is one of most important branch of applied mathematics andoperations research. It comes from an ancient problem, finding the minimized or maximized valueof one function or problem. In simple terms, the optimization problem is how to find the solutionto solve the problem. Especially, in the2ndhalf of20thcentury, with the great advances of societyand science, optimization theory became a new discipline. Driven by the rapid development ofcomputer technology, optimization theory has been applied to various area of society, such as carvehicle body structure design, aircraft cabin optimization, history matching for reservoir data, anddistribution logistics.Optimization algorithm for solving optimization problem has been a research focus ofmathematics for several centuries. From Newton proposed Newton method which was a kind ofgradient decent method in17thcentury, lots of great mathematicians had dedicated themselves tostudy newer and more efficient optimization algorithms and a number of excellent algorithmswere invented, for example, conjugate gradient method, quasi-Newton method, trust regionmethod, least squares method and so on. As these classic optimization algorithms processed fastand efficiently, they had been widely used.Recently, more and more people paid more attention to optimization algorithm. In2011, CCWResearch had published a report about optimization algorithm market named "2010-2011appliedmarket research report of information optimization algorithm". From the report, optimizationalgorithm had been used and researched from universities and research institutes to enterprises andgovernment in last three years. The amount procurement of optimization algorithm increasedevery year, and the increasing speed of market was more than35%each year. It's expected that themarket would be reached to230million Yuan in2013. So, optimization algorithms are not onlyimportant for research, but also bring huge economic benefits.However, the global search ability is poor for classic optimization algorithms, so it's easy to fallinto local minima when using this kind of algorithms, and lead to premature convergence. Theinitial states of optimization problem can also decide whether these algorithms can find optimalsolutions. As a result, the users of classic optimization algorithms have a good background inmathematics and a priori knowledge about the optimization problem. It's really a big limitation tothe application of these classic optimization algorithms. Since the1950s, with the greatdevelopment of computer technology and bionics, the research of swarm intelligence optimizationtheory became a focus, and a lot of swarm intelligence optimization algorithms were constantlyraised, such as genetic algorithms (GA), particle swarm optimization (PSO), and ant colonyalgorithm (ACO). Swarm intelligence optimization algorithms mimic the nature biological group behaviors, andthey have the following advantages compared to classic optimization algorithms: this kind ofalgorithms is a global optimization process and doesn't depend on the initial state; they can beapplied widely without prior knowledge on the optimization problems; the ideas and theimplements of these algorithms are quite simple, the steps are standardization, and it's veryconvenient to integrate them with other algorithms; these algorithms are based on the swarmintelligence theory, and they have very good potential parallelism.There is a common feature in swarm intelligence optimization algorithms. It's that fitness valueis used to exchange information in the population, and guides the population to close the optimalsolution. Therefore, a mount of fitness should be calculated in swarm intelligence optimizationalgorithms in order to find the optimal solution or an approximate one. However, when thecalculation of the fitness is quite complex, the time cost of this kind of algorithms will be too large.What's more, the fitness of optimization problems in the real world is often difficult to calculate.Addressing this problem, a series of solutions ware proposed in the paper.Inspired by k-means clustering based genetic algorithm (KMGA) and fitness inheritancestrategies based genetic algorithm (IGA), a genetic algorithm based on affinity propagationclustering (APGA) was firstly proposed. The basic idea of APGA is as followed: beforecalculating the fitness in GA, AP clustering is employed to cluster similar chromosomes firstly,and then the fitness values are estimated by the clustering information. A fitness estimationstrategy is also proposed in this paper. It's using the fitness of cluster center and the distance fromother chromosome's in the cluster to the cluster center to estimate the fitness value, a regulationfactor is introduced to this strategy to prevent oscillation in the estimation of fitness value. Asinherited the good features of AP clustering, stable, efficient, and determining clustering sizeautomatically, APGA overcame the shortage of KMGA and IGA as dependence on the initial stateand too large fitness estimation error. The experiments show that: when APGA, KMGA, IGA andclassic GA (CGA) were set same maximum iteration, APGA calculated least fitness value and theresult were closed to CGA; when the4algorithms calculated some number of fitness value, theoptimization accuracy and stability was better than other algorithms; and fitness estimation errorwas lower than others as well.After the study on pattern theory of GA, a novel fitness estimation strategy based on patterndiscovery was proposed, and an efficient GA (EGA) based on this strategy and APGA was alsoproposed. The fitness estimation strategy was originated from schema theorem and building blockhypothesis. During the pattern theory, short, low-order, above-average schemas (building block)receive exponentially increasing trials in subsequent generations. Under the operation of geneticoperators, building blocks would form longer, higher-order and higher fitness schema, and formoptimal solution in the end. In EGA, We maintained local best and worst chromosome sets, andcreated a strategy to discover the best and worst schema using the two sets. And then the schemaswere used to adjust the fitness value of chromosomes, including increasing the fitness value ofchromosomes which contained best schema and decreasing the fitness value of chromosomeswhich contained worst schema. The fitness correction strategy can promote the reproductionchance of good chromosomes; while at the same time accelerate the elimination of badchromosomes. It can also cover the shortage that the fitness values estimated by APGA always lower than cluster centers. Experiments proved that with the same number of iterations, the resultof EGA was closer to optimal solution than APGA, and the curve figures show that the fitnessestimation errors were much lower. There results could also prove the correctness of patterntheory.For some kinds of engineering optimization problem which the fitness function can't be defined,the calculation of fitness always needs to call other software to simulate, and then get a value toevaluate the chromosomes, but the simulation process is always time-consuming. In this situation,regression analysis was introduced to help estimating fitness value in GA, and support vectorregression (SVRGA) based GA was also proposed. It was different from former research that, wedidn't used GA to optimize the parameters of SVR or SVM, but use SVR to estimate fitnessvalues of partly chromosomes in order to reduce the calculation number of fitness values. SVR isa machine learning method which can get good performance with a small training set. Wemaintained a proper size training set in SVRGA. When the size of the set grew to a fix number, aSVR model would be trained each iteration. The majority of chromosomes' fitness values wouldbe estimated by the SVR model, other chromosomes' would be calculated really, and added thesechromosomes to the training set. Experiments show that, the training cost of SVR was quite lowwith the training set we maintained, and the estimation displayed well. So SVRGA's fitnessestimation accuracy was higher than KMGA and IGA, and the speed of SVRGA was also veryfast.In this paper, we also extended the fitness estimation strategies above to PSO, and proposedPSO based on affinity propagation clustering (APSO), efficient PSO (EPSO), and PSO based onSVR (SVRPSO). The idea of EPSO was learnt from pattern theory of GA. Although there was notconvergence theory in PSO, the performance of EPSO was proved to be better than APSO throughexperiments. From the experiments, it also can be seen that: these PSO could prevent most fitnesscalculation to speed up PSO; in the sight of algorithm result, EPSO is similar to SVRPSO andbetter than APSO. After analyzing the curve figures of fitness estimation error, it could be seenthat SVRPSO displayed well on the single peak and smooth function, while EPSO did well inmulti-peak function. The successful application of fitness estimation strategies to PSO had adirection meaning to design other efficient swarm intelligence algorithms.In the end of this paper, in order to verify the effect of our algorithms in the actual productionand research area, we applied EPSO, EGA and SVRGA to three different areas of practicalproblems respectively, which were the history matching for reservoir data, the dome structureoptimization under static stress and the prediction of E. coli chromosome supercoiling site.Regarding the problem of history matching for reservoir data, AP clustering effectively gatheredsimilar chromosomes which represented reservoir geological parameters, the clusteringinformation and the reservoir data which were get from reservoir numerical simulation were usedto estimate the fitness of a large number of chromosomes. Thereby EPSO reduced the number ofcalling reservoir numerical simulator, and accelerated the speed of history matching. For theproblem of dome structure optimization under static stress, we fully considered the characteristicsof dome structure and the bar material, and designed a continuous fitness function. Then EGA wasused to reduce the calling number of finite element static analysis, and also significantly increasedthe efficiency of the optimization algorithm. Regarding the prediction of E. coli chromosome supercoiling site, according to the characteristics of supercoiling site which described in theexisting literature, we designed a fitness function. Because the long coding in supercoiling siteprediction, just matched the dimension-independent characteristics of SVR, it was suitable forgetting results by SVRGA. And the results also show that the solving speed of SVRGA is fasterthan CGA. The three typical practical problems were employed to verify the effectiveness of thealgorithms we proposed in this paper, and it was proved that the algorithms possessed goodpractical potential.In summary, we have researched the problem how to estimate the fitness of genetic algorithmand particle swarm algorithm deeply, and have proposed a variety of fitness estimation strategy.The experimental results show that these algorithms can ensure the optimization accuracy is closeto the optimal solution at the same time can significantly reduce the fitness calculation times.The successful application of these algorithms in three different areas verified the efficiency andstability of our algorithms.