The Study On Intelligent Optimization Methods And Their Applications

The phenomena of adaptive optimization in the nature have always given us many metaphors. Creatures and natural ecological systems can solve the optimization problems with high degree of complexity to scientists satisfactorily and elegantly. Under this background, many intelligent optimization algorithms, which mimic the mechanism of the nature and creatures' behaviors, have emerged. They provide us new methods to tackle those NP-hard problems that are difficult for conventional optimization algorithms. Tasks assignment and scheduling is one of the key factors for parallel-distributed systems to get good performance. They are NP-hard problems. Assignment and scheduling algorithms based on intelligent optimization methods can tackle those problems effectively and efficiently. Three typical intelligent optimization algorithms, Genetic Algorithm (GA), Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO), are studied in this dissertation. Immune principles are used to improve their performance. Some novel, effective and efficient algorithms are designed for independent tasks assignment problem in heterogeneous computing environment and precedent-constrained tasks scheduling problem in homogeneous and heterogeneous environments.An ACO algorithm with immune characteristics is presented. Based on the basic principles of artificial immune systems, three immune operators, immune restrain operator, pheromone smooth operator and inject vaccine operator, are designed. In order to keep ACO from premature convergence, immune restrain operator and pheromone smooth operator are used to keep the diversity of ant colony. Inject vaccine operator is used to improve the algorithm's intensification ability. Using those immune operators, ACO algorithm can get better balance between exploration and exploitation. The simulation results on benchmark Traveling Salesman Problems (TSP) and tasks assignment and scheduling problem show that those immune operators can improve the performance of ACO algorithm significantly.On analyzing the difference between continuous PSO and Discrete PSO (DPSO), an effective DPSO is designed. Based on the characteristics of discrete variable, this paper redefined particle's position, velocity and their operation rules. In order to restrain premature stagnation, individual diversity of particle, micro-diversity and macro-diversity of particle swarm are defined. Repulsion operator and expand operator are designed to keep the diversity of particle swarm, and inject vaccine operator is defined to improve the algorithm's intensification ability. Using those operators, the proposed algorithm can get good balance between exploration and exploitation. The simulation results on benchmark TSP problem and tasks assignment and scheduling problem show that DPSO can be used to tackle those problems effectively and efficiently.Based on GA, ACO, DPSO and immune principles, using direct encoding method or indirect encoding method to encode solution into search space, thisdissertation presents some effective and efficient algorithms for tasks assignment problem in heterogeneous computing systems. The presented immune genetic algorithm, immune ant colony optimization and immune discrete particle optimization, which use direct encoding method, search the optimal solution in solution space directly. The proposed immune hybrid genetic algorithm, segmented immune hybrid ant colony optimization and immune hybrid discrete particle optimization, which use indirect encoding method, are the combination of list assignment algorithm and intelligent optimization methods. Using the tasks assignment sequence as search space, they search an optimal assignment sequence first, and then the sequence is mapped into a solution using minimum completion time algorithm. Immune principles are used to improve the diversification and intensification ability in those algorithms. The simulation results of those algorithms show that immune principles can improve balance between exploration and exploitation for intelligent optimization algorithms, and intelligent optimization algorithms can be used to tackle tasks assignment problems effectively and efficiently.Based on GA, ACO, DPSO and immune principles, using direct encoding method or indirect encoding method to encode solution into search space, this dissertation presents some effective and efficient algorithms for precedent-constrained tasks scheduling problem in parallel-distributed systems. The presented immune genetic algorithm, which uses direct encoding method, uses immune mutation operator to keep the diversity of population, and a one-cut-point learning crossover operator, based on Lamarckian theory, is designed to improve the exploitation ability of GA. The proposed indirect coded hybrid genetic algorithm, ant colony optimization and discrete particle optimization, which use indirect encoding method, are the combination of list scheduling algorithm and intelligent optimization methods. Using the tasks scheduling priority queue as search space, they search an optimal scheduling priority queue first, and then the priority queue is mapped into a solution using earliest finish time processor first algorithm. The simulation results of those algorithms show that immune principles can improve balance between exploration and exploitation for intelligent optimization algorithms, and intelligent optimization algorithms can be used to tackle precedent-constrained tasks scheduling problems effectively and efficiently.