Research On Memetic Algorithm And Its Engineering Applications

Recently, simulating the phenomena of nature to solve computation problems is becoming a hot research topic and a new academic framework based on Swarm Intelligence is formed accordingly. Memetic algorithm is based on human culture evolution theory. The algorithm can provide efficient solutions for optimization problems through intelligence generated from culture transmission activities such as information selection, information process and information change. This work concentrates on memetic algorithm theory and its engineering applications such as continuous function optimizations, travelling salesman problem with time restraint and dynamic scheduling problem.Firstly, the memetic algorithm theory is introduced in detail and its developments are reviewed. The algorithm optimization mechanism, the operation flow and its research hotspots and difficulties are expatiated systemically. The basic applications of memetic algorithm and its engineering applications are summarized.Secondly, by the research of continuous function optimizations, a new memetic algorithm based on climbing method as the local search is proposed for solving these problems. For proving the strongpoint of the memetic algorithm, it is used for solving the optimization problems of Schaffer function, De Jong function and Six-hump Camel Back function. According to the optimal solution, the memetic algorithm is better than genetic algorithm and Newton's iteration method.Thirdly, the travelling salesman problem with time restraint is introduced in detail. A new memetic algorithm based on two local optimization operators is proposed for solving this problem. During the algorithm flow, it uses order crossover and two-block-exchange mutation, then after each crossover and mutation operation, it adopts greed recessive variation or recursive arc insertion by the random parameter. Experimental results demonstrate that the memetic algorithm can solve this problem very effective and it has a good robustness.Finally, the theory of dynamic scheduling problem and a rolling window mechanism is investigated in detail. The rolling horizon of dynamic scheduling is analyzed systemically. A memetic algorithm based on rolling-horizon procedure to solve the dynamic job-shop scheduling is proposed. In this procedure, periodic and event driven rescheduling strategies are employed to decompose the scheduling process into a series of continual and static scheduling problems, and the memetic algorithm is applied to solving each of the static scheduling problems. The order crossover and a new mutation based on neighborhood search are employed in the memetic algorithm. After each crossover and mutation operation, an improved simulated-annealing algorithm is utilized for local search. In allusion to the dynamic event of workpiece delay and insert, a modified Job-shop benchmark instance is tested, and the simulation results validate the effectiveness of the proposed strategy.