Intelligent Optimization Algorithm And Its Application On TSP And Minimal Hitting Sets Problem

The intelligent algorithm is one computational method which profits fromand uses the natural phenomenon in the nature or organism's some kind ofprinciple and the mechanism, and it has the auto-adapted environmentability. The key weighed the intelligent degree of intelligence algorithm lieswith intelligence algorithm's learning capability when it processes actualobject. As intelligent algorithm important research content intelligentoptimization algorithm, except classical Genetic Algorithm and simulatedannealing, in recent years has presented more new intelligent agent, such asImmune algorithms, ant colony algorithms, Particle Swarm Optimizationand so on.Natural evolution is an optimization process based on population.Evolutionary Computation is established based on natural choice andgenetics, including mainly Genetic Algorithm,Evolutionary Programmingand Evolutionary Strategies.In the overall the optimized method may divide into two big kinds:determined methods and stochastic methods. The determined methods mayextremely quick, but is easy to fall into local minimum. On the contrary, thestochastic methods is not easy to fall into local minimum, but in the limitedstep one stochastic method has not been allowed to guarantee found the globalminimum. In all optimized method, the simulated annealing method isconsidered as one of most effective methods. By establishing acorrespondence between the solutions and the physical states, we canintroduce a solution method in the field of combinatorial optimization basedon a simulation of the physical annealing process. The resulting method iscalled simulated annealing.Ant colony algorithm is a new type of simulated evolutionary algorithms,which is used to solve some NP-hard combinatorial optimization problemsthrough simulating the process of ants searching for food. This algorithm isproposed first by Italian scholar M.Dorigo, V.Maniezzo, A.Colorini in 1991,called ant colony system. And there are better results to apply this algorithmto solve the TSP, the assignment problem and job-shop scheduling. Thisalgorithm has several characteristics such as positive feedback, distributedcomputing and combination with certain heuristics. Positive feedbackmakes it easier to find better solutions. Simulations demonstrate that it is arobust algorithm based on population and a promising way for optimization.Biological immune system is a highly parallel adaptive information learningsystem, which can identify and remove the antigenic invading the body.This system can learn, remember and adjust adaptively to keep thestabilization inside the body. According to the prototype of living body'simmune system, AIS (Artificial Immune System) is proposed. Based on themain function of immune system, the typical algorithms are described, suchas immune algorithm, negative and colonel selection algorithms, immuneevolutionary algorithm, AIS-neural network mix intelligent system, fuzzyimmune system and so on. Immune algorithms (IAs) are optimizationtechniques that imitate immune systems in an organism. IAs are able toobtain a multiple quasi-optimum solution while maintaining the populationdiversity compared with GAs. Immune algorithm has become a hotspot inthe area of computational intelligence.Particle Swarm Optimization (PSO) algorithm was brought forward byDr.Eberhart and Dr.Kenney in 1995. It was a population based stochasticmethod motivated by the social behavior of bird flock and fish school. Thealgorithm completes the optimization through following the personal bestsolution of each particle and the global best value of the whole swarm. Itfinds optimal regions of complex search spaces through the interaction ofindividuals in a population of particle. PSO shares many similarities withEA&GA. Such as the system is initialized with a population of randomsolutions and searches for optima by updating generations and themechanism of iteration. PSO can be implemented with ease and fewparameters need to be tuned. It has been successfully applied in many areas,and has become the hotspot of evolutionary computation.Traveling Salesman Problem (TSP) is a well-known NP-completedcombinatorial optimization problem. By now, TSP has been well studied bymany approaches. We designed new PSO to solve TSP. Each particleexpresses a feasible way, Its speed is composed by a series of sub-ways,Through turning over the particles the sub-ways in its speed becomes itsown part. Simultaneously each generation one particle of population carriesout the order preserving of the gene section operation. And four methods ofcomputing speeds are produced.In section 3, particle swarm optimization (called PSO) algorithm is used tocompute hitting sets in model-based diagnosis. Through putting forwardnew meanings to the velocity of the PSO and designing a new motionmethod for the particles, we carry out the search for minimal hitting setsunder the situation of not increase other assistant operations. Because thePSO algorithm has the advantages of structure simple, flat-out and quick, soit can be used to compute the large-scale minimal hitting sets problem.From the test of the instances, it can be seen that the larger the scale of theproblem, the smaller the ratio of the particle number that is searched for andthe particle total amount of the solution space. It expresses that this methodis more suitable for computing large-scale minimal hitting sets problem. Atthe same time, the influence of parameter setting on algorithm performanceis discussed in this paper.In section 4, an improved genetic algorithm (called GA) is used to computeminimal hitting sets. In order to improve the algorithm's efficiency, elitestrategy was introduced base on the standard GA. At the same time,minimization operations were added during the evolution process so that thesolutions gotten are all minimal hitting sets. In order to prove the validities,we tried different cross and mutation operations for different examples,analyzing their effects in computing the minimal hitting sets, lots ofstrategies' minimal operations were tested and making some comparisonsbetween them. Finally, comparisons are made between our algorithm andother approaches for computing the minimal hitting sets.