Genetic algorithm is a novel optimization technique for solving constrained optimization problems. The penalty function methods are the popular approaches because of their simplicity and ease of implementation. Penalty encoding method needs more generations to get good solutions because it causes invalid chromosomes during evolution. In order to advance the performance of Genetic Algorithms for solving production allocation problems, this paper proposes a new encoding method, which applies the upper/lower bound concept of dynamic programming decision path on the chromosome encoding of genetic algorithm, that encodes constraints into chromosome to ensure that chromosomes are all valid during the process of evolution. Utilization of the implicated parallel processing characteristic of genetic algorithms to improve dynamic programming cannot guarantee to solve complex problems in the polynomial time. Additionally, a new simultaneous crossover and mutation operation is proposed to enable the new method to run correctly following the standard genetic algorithm procedures. This approach is evaluated on some test problems. Solutions obtained by this approach indicate that our new encoding genetic algorithms certainly accelerate the performance of the evolution process.
The production allocation problem is a constrained optimization problem and can be recognized as a NP-hard problem (Garavelli, Okogbaa, & Violante, 1996), such that solving this problem within polynomial time using general algorithms is impossible. Using iterative and random search methods, which involves parallel processing, an evolutionary process has a powerful solution searching capability. Genetic Algorithms are probabilistic search algorithms, which mimic biological evolution to produce gradually better offspring solutions. Each solution to a given problem is encoded by a string of bits that represents an individual in a population. Genetic Algorithms assign a fitness value to every individual according to the quality of the solution which represents. An individual having a better fitness value in the population is more able to survive into the next generation and vice versa. Every generation must through three main genetic operations, which are selection, crossover and mutation. In genetic algorithm, a satisfactory solution is not obtained. The evolutionary process continues as long as the number of iteration.
Genetic Algorithms have been successfully applied to the constrained optimization problems such as Traveling Salesman Problem (Chatterjee et al., 1996 and Katayama et al., 2000), Timetable Problem (Burk & Newall, 1999), Quadratic Assignment Problem (Ahuja et al., 2000, Nissen, 1994, Schnecke and Vornberger, 1997 and Tate and Smith, 1995), Job Shop Scheduling Problem (Cheng et al., 1996, Cheng et al., 1999, Della et al., 1995, Wang and Zheng, 2001 and Zhou et al., 2001), Airline Crew Scheduling Problem (Ozdemir & Mohan, 2001), and others.
The penalty encoding method perhaps is the most popular approach used in Genetic Algorithms for constrained optimization problems, because of its simplicity and ease of implementation (Chau, 2004, Contreras et al., 2005, Deb, 2000, Gen and Cheng, 1996, Ji, 2005 and Michalewicz et al., 1996). Using this conventional encoding method to solve constrained optimization problems may waste much time and lead to an inefficient performance because it does not narrow down the search space of the problems by encoding any constraints into the chromosome. This study elucidates a novel means of encoding Genetic Algorithms to solve the production allocation problem. This new method, called the dynamic programming decision path encoding method, can greatly shrink the search space and lead to an efficient performance. This new encoding method applies the upper/lower bound concept of dynamic programming decision path on the chromosomes to ensure that chromosomes are all valid during the process of evolution. Using the implicated parallel processing characteristics of Genetic Algorithms to improve dynamic programming can not guarantee to solve complex problems in polynomial time. A new crossover and mutation operation is proposed to enable the new method of encoding chromosomes to run correctly with the standard genetic algorithm procedures. This approach is evaluated for some test problems of various sizes. Solutions obtained by this approach are efficient.
Genetic Algorithms are suitable for solving the generalized production allocation problem which is a NP-hard and constrained optimization problem. Using the penalty function to guide the progress of genetic algorithms may waste many costs the handle invalid solutions during evolution. This is because the penalty encoding method can’t narrow down the solution searching range. This study proposes a new dynamic programming decision path encoding method with the corresponding crossover and mutation operator that can efficiently reduce the solution search space as it encodes constraints into the chromosome. We compare the computational results of our new encoding (which encodes two constraints, markets’ demand and plants’ capacity, into the chromosome), with the combination encoding (which encodes one constraint, markets’ demand, into the chromosome), the penalty encoding (which makes use of the penalty function to guide the evolution process) of genetic algorithms and integer programming for the production allocation problems. The experimental consequences reveal that our new encoding method is superior than the others in searching good solutions. And the combination encoding is better than the penalty encoding. Moreover, the integer programming just only can get feasible solutions and these feasible solutions are worse than the solutions which are obtained by Genetic Algorithms. Future research will apply this efficient method to other constrained optimization problems.
