Catálogo de publicaciones - libros

Minimal Switching Graph (MSG) is a graph-theoretic representation of the constrained via minimization problem — a combinatorial optimization problem in integrated circuit design automation. From a computational point of view, the problem is NP-complete. Hence, a genetic algorithm (GA) was proposed to tackle the problem, and the experiments showed that the GA was efficient for solving large-scale via minimization problems. However, it is observed that the GA is sensitive to the permutation of the genes in the encoding scheme. For an MSG problem, if different permutations of the genes are used the performances of the GA are quite different. In this paper, we present a new GA for MSG problem. Different from the original GA, this new GA has a self-adaptive encoding mechanism that can adapt the permutation of the genes in the encoding scheme to the underlying MSG problem. Experimental results show that this adaptive GA outperforms the original GA.

Here is presented an improved simulated annealing (SA) method for solving the combinatorial sub-problem of profit-based unit commitment (UC) problem in electric power and energy systems. The UC problem is divided into a combinatorial sub-problem in unit status variables and a non-linear programming sub-problem in unit power output variables. The simulated annealing method with an improved random perturbation of current solution scheme is proposed to solve the combinatorial sub-problem. A simple scheme for generating initial feasible commitment schedule for the SA method to solve the combinatorial problem is also proposed. The non-linear programming sub-problem is solved using the sequential quadratic programming (SQP) technique. Several example systems are solved to validate the robustness and effectiveness of the proposed technique for the profit-based UC problem.

Among the modern heuristic methods, simulated annealing (SA) and genetic algorithms (GA) represent powerful combinatorial optimization methods with complementary strengths and weaknesses. Borrowing from the respective advantages of the two paradigms, an effective combination of GA and SA, called Genetic Simulated Algorithm (GASA), is developed to solve the job shop scheduling problem (JSP). This new algorithm incorporates metropolis acceptance criterion into crossover operator, which could maintain the good characteristics of the previous generation and reduce the disruptive effects of genetic operators. Furthermore, we present two novel features for this algorithm to solve JSP. Firstly, a new full active schedule (FAS) based on the operation-based representation is presented to construct schedule, which can further reduce the search space. Secondly, we propose a new crossover operator, named Precedence Operation Crossover (POX), for the operation-based representation. The approach is tested on a set of standard instances and compared with other approaches. The Simulation results validate the effectiveness of the proposed algorithm.

With the intrinsic properties of constraint satisfaction problems (CSPs) in mind, several behaviors are designed for agents by making use of the ability of agents to sense and act on the environment. These behaviors are controlled by means of evolution, so that multiagent evolutionary algorithm for constraint satisfaction problems (MAEA-CSPs) results. To overcome the disadvantages of the general encoding methods, the minimum conflict encoding is also proposed. The experiments use 250 benchmark CSPs to test the performance of MAEA-CSPs, and compare it with four well-defined algorithms. The results show that MAEA-CSPs outperforms the other methods. In addition, the effect of the parameters is analyzed systematically.