Skip to main content
main-content

Über dieses Buch

Since the introduction of genetic algorithms in the 1970s, an enormous number of articles together with several significant monographs and books have been published on this methodology. As a result, genetic algorithms have made a major contribution to optimization, adaptation, and learning in a wide variety of unexpected fields. Over the years, many excellent books in genetic algorithm optimization have been published; however, they focus mainly on single-objective discrete or other hard optimization problems under certainty. There appears to be no book that is designed to present genetic algorithms for solving not only single-objective but also fuzzy and multiobjective optimization problems in a unified way. Genetic Algorithms And Fuzzy Multiobjective Optimization introduces the latest advances in the field of genetic algorithm optimization for 0-1 programming, integer programming, nonconvex programming, and job-shop scheduling problems under multiobjectiveness and fuzziness. In addition, the book treats a wide range of actual real world applications. The theoretical material and applications place special stress on interactive decision-making aspects of fuzzy multiobjective optimization for human-centered systems in most realistic situations when dealing with fuzziness.
The intended readers of this book are senior undergraduate students, graduate students, researchers, and practitioners in the fields of operations research, computer science, industrial engineering, management science, systems engineering, and other engineering disciplines that deal with the subjects of multiobjective programming for discrete or other hard optimization problems under fuzziness. Real world research applications are used throughout the book to illustrate the presentation. These applications are drawn from complex problems. Examples include flexible scheduling in a machine center, operation planning of district heating and cooling plants, and coal purchase planning in an actual electric power plant.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract
Genetic algorithms, originally called genetic plans, were initiated by Holland, his colleagues, and his students at the University of Michigan in the 1970s as stochastic search techniques based on the mechanism of natural selection and natural genetics. In his 1975 monograph Adaptation in Natural and Artificial Systems [75], Holland presented genetic algorithms as an abstraction of biological evolution with a theoretical framework for adaptation. In the same year, De Jong completed his dissertation An Analysis of the Behavior of a Class of Genetic Adaptive Systems [46]. De Jong considered genetic algorithms in a function optimization setting, and since then genetic algorithms have attracted considerable attention as global methods for complex function optimization.
Masatoshi Sakawa

Chapter 2. Foundations of Genetic Algorithms

Abstract
This chapter is devoted to the foundations of the genetic algorithms that will be used in the remainder of this book. Starting with several basic notions and definitions in genetic algorithms, fundamental procedures of genetic algorithms are outlined. The main idea of genetic algorithms, involving coding, fitness, scaling, and genetic operators, is then examined. In the context of bit string representations, some of the important genetic operators are also discussed by putting special emphasis on implementation issues for genetic algorithms.
Masatoshi Sakawa

Chapter 3. Genetic Algorithms for 0–1 Programming

Abstract
In this chapter, genetic algorithms with double strings (GADS) as developed for multidimensional 0–1 knapsack problems are discussed in detail. Through the introduction of a double string representation and the corresponding decoding algorithm, it is shown that a potential solution satisfying constraints can be obtained for each individual. Then the GADS are extended to deal with more general 0–1 programming problems involving both positive and negative coefficients in the constraints. Especially, new decoding algorithms for double strings using reference solutions both without and with the reference solution updating procedure are introduced so that each individual is decoded to the corresponding feasible solution for the general 0–1 programming problems. The detailed comparative numerical experiments with a branch and bound method are also provided.
Masatoshi Sakawa

Chapter 4. Fuzzy Multiobjective 0–1 Programming

Abstract
In this chapter, as a natural extension of single-objective 0–1 programming problems discussed in the previous chapter, multiobjective 0–1 programming problems are formulated by assuming that the decision maker may have a fuzzy goal for each of the objective functions. Through the combination of the desirable features of both the interactive fuzzy satisficing methods for continuous variables and the genetic algorithms with double strings (GADS) discussed in the previous chapter, an interactive fuzzy satisficing method to derive a satisficing solution for the decision maker is presented. Furthermore, by considering the experts’ imprecise or fuzzy understanding of the nature of the parameters in the problem-formulation process, the multiobjective 0–1 programming problems involving fuzzy parameters are formulated. Through the introduction of extended Pareto optimality concepts, an interactive decision-making method for deriving a satisficing solution of the decision maker from among the extended Pareto optimal solution set is presented together with detailed numerical examples.
Masatoshi Sakawa

Chapter 5. Genetic Algorithms for Integer Programming

Abstract
This chapter is the integer version of Chapter 3, and genetic algorithms with double strings (GADS) for 0–1 programming problems are extended to deal with integer 0–1 programming problems. New decoding algorithms for double strings using reference solutions with the reference solution updating procedure are proposed especially so that individuals are decoded to the corresponding feasible solution for integer programming problems. The chapter also includes several numerical experiments.
Masatoshi Sakawa

Chapter 6. Fuzzy Multiobjective Integer Programming

Abstract
This chapter can be viewed as the fuzzy multiobjective version of Chapter 5 and is devoted to a integer generalization along the same lines as in Chapter 3. Through the use of genetic algorithms with double strings (GADS), considerable effort is devoted to the development of fuzzy multiobjective integer programming as well as fuzzy multiobjective integer programming with fuzzy numbers together with several numerical experiments.
Masatoshi Sakawa

Chapter 7. Genetic Algorithms for Nonlinear Programming

Abstract
In this chapter, after introducing genetic algorithms for nonlinear programming including the original GEnetic algorithm for Numerical Optimization of COnstrained Problems (GENOCOP) system for linear constraints, the coevolutionary genetic algorithm, called GENOCOP III, proposed by Michalewicz et al. is discussed in detail. Realizing some drawbacks of GENOCOP III, the coevolutionary genetic algorithm, called the revised GENOCOP III, is presented through the introduction of a generating method of an initial reference point by minimizing the sum of squares of violated nonlinear constraints and a bisection method for generating a new feasible point on the line segment between a search point and a reference point efficiently. Illustrative numerical examples are provided to demonstrate the feasibility and efficiency of the revised GENOCOP III.
Masatoshi Sakawa

Chapter8. Fuzzy Multiobjective Nonlinear Programming

Abstract
In this chapter, attention is focused on not only multiobjective nonlinear programming (MONLP) problems but also MONLP problems with fuzzy numbers. Along the same lines as in Chapters 4 and 6, through the revised GENOCOP III, some refined interactive fuzzy MONLP and fuzzy MONLP with fuzzy numbers are developed for deriving a satisficing solution for the decision maker.
Masatoshi Sakawa

Chapter 9. Genetic Algorithms for Job-Shop Scheduling

Abstract
This chapter considers job-shop scheduling problems, which determine a processing order of operations on each machine in order to minimize the maximum completion time. By incorporating the concept of similarity among individuals into the genetic algorithm that uses a set of completion times as individual representation and the Giffler and Thompson algorithm-based crossover, an efficient genetic algorithm for job-shop scheduling problems is presented. As illustrative numerical examples, 6 x 6, 10 x 10, and 15 x 15 job-shop scheduling problems are considered. The comparative numerical experiments with simulated annealing and the branch and bound method for job-shop scheduling problems are also demonstrated.
Masatoshi Sakawa

Chapter 10. Fuzzy Multiobjective Job-Shop Scheduling

Abstract
In this chapter, by considering the imprecise or fuzzy nature of the data in real-world problems, job-shop scheduling problems with fuzzy processing time and fuzzy due date are formulated. On the basis of the agreement index of fuzzy due date and fuzzy completion time, the formulated fuzzy job-shop scheduling problems are interpreted to maximize the minimum agreement index. Furthermore, multiobjective job-shop scheduling problems with fuzzy due date and fuzzy processing time are formulated as three-objective problems. Having elicited the linear membership functions reflecting the fuzzy goals of the decision maker (DM), the fuzzy decision of Bellman and Zadeh is adopted for combining them. The genetic algorithm introduced in the previous chapter is extended for solving the formulated problems.
Masatoshi Sakawa

Chapter 11. Some Applications

Abstract
It is now appropriate to demonstrate some application aspects of genetic algorithms. As examples of Japanese case studies, we present some applications of genetic algorithms to flexible scheduling for a machining center, in the operation planning of district heating and cooling (DHC) plants, and in the coal purchase planning in a real electric power plant.
Masatoshi Sakawa

Backmatter

Weitere Informationen