PSO And Its Application On Function Optimization And Path Optimization

Evolutionary compution includes genetic algorithm ,evolutionarystrategy and evolutionary programming.These algorithms is all intelligentalgorithm. The intelligent algorithm is one computational method whichprofits from and uses the natural phenomenon in the nature or organism'ssome kind of principle and the mechanism, and it has the auto-adaptedenvironment ability. The key weighed the intelligent degree of intelligencealgorithm lies with intelligence algorithm's learning capability when itprocesses actual object. In recent years more new intelligent agent has beenpresented, such as ant colony algorithms, Particle Swarm Optimization andso on.It is clear that when there is an optimization problem, the goal is to findthe best possible solution to the given problem. An optimization task consistsof two distinct steps: creating a model of the problem and using that model togenerate a solution. Traditionally, solutions to optimization problems oftenusing either problem specific heuristics or variants of the local-search methodthat iteratively refines a single candidate solution to the problem. Thetraditional methods are not robust with respect to problem-type and oftenonly work on well-defined problems where the number of possible solutionsis not too large. The traditional methods have the unavoidable weakness thatthey cannot guarantee to complete their computations within a reasonableamount of time on hard and complex problems. (For example, theirtime-complexity is exponential on NP-hard problems).We get an approximatesolution to an exact model by using optimization algorithm. For practical use,optimization algorithm is often superior to the traditional methods.Population-based optimization algorithms have shown capabilities ofapproximating optimal solutions to these real-world problems within areasonable amount of time. The best known of these algorithms is theevolutionary algorithm (EA), which is inspired by natural evolution.Furthermore, a new algorithm, the particle swarm optimization (PSO)algorithm is also a population-based search-algorithm. Conceptually, thereare, however some differences between the PSO and EA. Particles stay aliveand "inhabit" the search space during the run, whereas in EA the individualsare replaced each generation. Furthermore, the objective is reached throughcooperative search in particle swarms rather than competitive search as inEA.PSO was introduced by Dr.Eberhart and Dr.Kenney in 1995. Thealgorithm is a random searching algorithm based swarm intelligence in nature.Further, the particle swarm has roots in artificial life and in evolutionarycomputation. The swarm consists of a population of individuals that representivsolutions to the optimization problem. Through an iterative and modificationof these solutions, we search for an optimal solution.Each particle keeps trackof its coordinates in the problem space which are associated with the bestsolution it has achieved so far.This value is called Pbest.Meanwhile theglobal best value that is obtained so far by any particle in the swarm isrecorded.This value is called Gbest. In each iteration,the particle changes itsvelocity and position toward its Pbest and Gbest. During the search, theparticles exchange information about their positions and fitness values. Thiscommunication results in, that the swarm learn and refine its knowledgeabout the search, and move towards the good search space areas. This isanalogous to flocks of birds flying and searching for food. The particles havememory, which is important to the algorithm. Compared to GA, theadvantages of PSO are that PSO is easy to implement and there are fewparameters to adjust. It can converge to the optimal area more probability andBe adept in functions optimization.In this thesis, we summarize PSO algorithm and its development. In 2chapter, we present the original version of PSO with maximum velocity.Further, we introduce the difference of between PSO and EA. PSO parametercontrol is also introduced. At last, we analyse movement track of the particleunder some condition. PSO algorithm has major weakness: It suffers fromlocal optimal area easily. For this weakness, lots of improved ways ispresented in 3 chapter. For example, in 3.1 section we present thefundamental inertia-weight model. In 3.2 section PSO withconstriction-factor is presented. we bring forward a modification of PSO inwhich it gives the new definition of global extreme value in original PSOalgorithm's velocity update formula and it enlarges or shrinks fitness valueproperly. This way can avoid getting struck at local optima effectively. Byenlarging or shrinking fitness value and random ruler determine a certainparticle as global best value .This way alters information exchangemechanism of the particle which makes the particle keep variety. Theexperiment results demonstrate that proposed algorithm is superior to originalPSO algorithm obviously under given condition. The algorithm isimplemented easily and is of great application value.Firstly, PSO is used in continuous functions optimization. Therefore, itsapplication on other problems is presented in later section. In 4 chapter, PSOused in clustering problem is presented. After analyzing the disadvantages ofthe classical k-means clustering algorithm, this section introduced a novelk-means clustering based on PSO. The experimental results show that thealgorithm not only avoids the local optima and is robust to initialization, butalso increases the convergence speed and has global searching capability. Inthis thesis, path planning for mobile robot based on PSO is presented. In 5.1section, a novel path planning approach is presented, in which theMAKLINK graph is built to describe the working space of the mobile robot,the Dijkstra algorithm is used to obtain the shortest path from the start pointto the goal point in the graph, and PSO is adopted to get the best path.Simulation results show that this method is effective and can meet thereal-time demands of mobile robot navigation. This Thesis proposes a newapplication of PSO on maze problem. We accomplished algorithmic modelfor maze problem and proposed improvement of maze problem. Theexperiments show it can achieve good results.Anyway,the main work of this thesis lies in:1. Make a detailed introduction of background and development of PSO2. Propose NPSO algorithm and it is effective on function problem3. Proposes a new application of PSO on maze problemAt last, we make an overview of future work.