New Efficient Encoding Method of Genetic Algorithms for Resource/Production Allocation Problems
| Autor: | Ying-Hua Chang, 張應華 |
|---|---|
| Rok vydání: | 2003 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 91 This study proposes some efficient encoding evolutionary algorithms to solve the generalized resource allocation problem. First of all, we propose a novel efficient means of encoding genetic algorithms to solve the simple resource allocation problem. The problem relates to allocating limited resources across activities to maximize the return from them. The first proposed encoding method, combination encoding, can reduce the searching space of solutions because of encoding one constraint in the chromosome and thus exhibits higher performance. It need only involve a few more generations to yield sufficiently good solutions when the number of activities is increased. The penalty encoding method, however, requires many more generations to yield the same solutions. Additionally, a new simultaneous crossover and mutation operation is proposed to enable the new method of encoding chromosomes run correctly following standard genetic algorithm procedures. In addition to the mathematical certification, the performance of this approach is evaluated on some test problems of various variable sizes. Solutions obtained by this approach are always efficient. Due to the rapid worldwide economic development, global competition is increasing the importance of effectively coordinating production planning among the subsidiaries of multinationals. In a competitive global environment, managing the distributed production plants of an international company is a significant challenge and frequently becomes a strategic issue. Hence, numerous international companies have developed more complex and expansive planning systems for their global operations. These plans involve varying the location of manufacturing according to market demand, and aim to minimize costs for a multinational company subject to capacity constraints and market requirements. This paper also demonstrates the feasibility of successfully applying genetic algorithms to the production allocation problem, but requires the use of an efficient encoding method and adaptive operation mode. The new efficient encoding method can significantly reduce the search space of solutions and obtain a high performance. Therefore, this study presents another new approach, called the path-encoding method, which encodes two constraints into the chromosome and adapts the idea of dynamic programming for genetic algorithms to enhance the performance of evolutionary process. To allow correct running of the efficient encoding method through evolution procedures, a specialized path crossover and mutation operation is simultaneously proposed herein. The NP-hard production allocation problem is used to evaluate the effectiveness of the approach. This experiment compares the proposed approach to the combination-encoding method, the penalty-encoding method and integer programming. The computed results show that the proposed approach is always feasible and outperforms the others because it narrows the solution search space effectively. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|