Research On Evolutionary Algorithm For Assembly Sequence Planning

In traditional manufacturing，assembly tasks account for about50%of totalproduction time and more than20%of total manufacturing cost. It is an important factorthat determines the quality and cost of product assembly. Reasonable assemblysequence planning(ASP) is an important factor in improving product’s quality andreducing production cost. Evolutionary algorithm (EA) as the representative of theintelligent algorithm and geometric reasoning method are two typical methods forsolving ASP problem. Because ASP is a NP problem, the geometric reasoning methodwill inevitably bring about combinatorial explosion problem. Ordered binary decisiondiagram (OBDD) which is a new type of graph data structure, has the advantages ofhigh compactness and ease of operation. It is an effective technical to slow or avoidstate complexity of combinatorial problem in part. Geometric reasoning method ofassembly sequence based on OBDD can solve larger ASP, but still unable to overcomethe combinatorial explosion problem. EA is a kind of efficient approximationalgorithms for solving large-scale combinatorial optimization problems, theevolutionary algorithms for solving ASP can overcome the combinatorial explosionproblem, but they are still difficult to effectively make use of the assembly experienceand knowledge. EA based on the data structure of an array or set needs much storagespace and has a lot of blind search. In order to overcome the shortages，several novelEAs are proposed for ASP in the dissertation. Similar EA is also designed for a kind ofconstraint satisfaction problem(CSP). The main research contents are as follows:1. Typical evolution algorithm (such as simulated annealing，genetic algorithm andso on) is difficult to make use of individual assembly experience and assemblyknowledge. A multi-agent co-evolution algorithm is proposed for ASP, where learning，cooperative，competition，mutation operators of agent are designed and assemblyexperience of public knowledge and private knowledge are constructed. Agents caneffectively make use of the knowledge of assembly body and assembly experience.They share private knowledge through adjective field. In addition，according to thecharacteristics of ASP based on connector，a multi-agent evolutionary algorithm forASP based on connector is proposed. Simulation results show that two algorithms havebetter performance than other similar EAs.2. Multi-agent evolutionary algorithm makes use of constraints and assemblyexperience through knowledge which is some blindness. Inspired by self-assemblycalculation, in order to generate assembly sequences which meet basic constraints, evolutionary algorithms are proposed based on the assembly calculation for ASP. Anew evolutionary operator-growth operator is designed in each individual. Growthbased on assembly calculation observes assembly constraints in the process of evolutionto reduce the blindness search. In addition，combined with multi-agent technology，thisdissertation proposed a multi-agent evolutionary algorithm for ASP based on assemblycalculation. Experiments show two algorithms have better performance than othersimilar EAs.3. Most of the assembly model of ASP for EA is an array or matrix type. OBDDimplicit expression of assembly model can save storage space. Its data model alsofacilitates implicit parallel search. In order to save the data storage space and improvethe search performance of evolutionary algorithm, this dissertation proposed anevolutionary algorithm based on OBDD symbol technology. Two operators of randomrecombination and heuristic reorganization are realized and heuristic reorganization hasthe characteristics of assembly calculation. Compared with the traditional evolutionaryalgorithm，simulation results show the algorithm can effectively save the data storagespace and make use of a symbol technology hidden parallel search ability to improve itsperformance.4. In order to test scalability of evolutionary algorithm based on assemblycalculation and make more research, inspired by the assembly calculation of titlecomputational model, a novel evolutionary algorithm is suggested for solving constraintsatisfaction problem by solving TSP and n-queen problems. Assembly calculationmodel and evolutionary rules are designed accordingly. The generation of individualsneed not synchronous. The process is controlled by the assembly model and controlrules. Simulation results show that the novel algorithm has better performance for CSPthan other similar EAs.