Fuzzy genetic algorithms for combinatorial optimisation problems

• Auteur principal: Varnamkhasti, Mohammad Jalali
• Format: Thèse
• Langue: anglais
• Publié: 2012
• Sujets: Genetic algorithms; Combinatorial optimization
• Accès en ligne: http://psasir.upm.edu.my/id/eprint/32238/1/IPM%202012%201R.pdf

The Genetic Algorithms (GAs) have been very successful in handling optimization problems which are difficult. However, the fundamental problem in GAs is premature convergence and it is strongly related to the loss of genetic diversity of the population. This thesis aims at proposing some technique to tackle the premature convergence of GAs by controlling the population diversity. Firstly, a new sexual selection mechanism which utilizing mate chromosome during selection is proposed. The female chromosome is selected by standard tournament selection while the male chromosome is selected based on the hamming distance from the selected female chromosome, fitness value or the active genes. Fuzzy Logic Controllers (FLCs) are considered as knowledge-based systems, incorporating human knowledge. The second technique focuses on controlling the GA parameters by applying the FLC, thus creating a new variant of GA called Fuzzy Genetic Algorithm (FGA). In each generation, the diversity of studied population is measured in terms of the phenotype and genotype properties. Then the selection of crossover and mutation operators together with their probabilities are achieved by running the FLCs based on the diversity of the population. The proposed sexual selection and the FGAs are applied to combinatorial optimization problems specifically to those involving selection problems. We particularly focus on two problems: multidimensional 0/1 knapsack problems and p-median facility location problems. The goal of a multidimensional 0/1 knapsack is to boost the sum values of the items to be chosen from some specified set by means of taking multiple-resource restrains into consideration. In the p-median problem, the aim is to choose the positions of the p facilities in order to cover n demand points such that the summation of distances from each facility to each corresponding demand point is brought to a minimum. Extensive computational experiments are carried out to assess the effectiveness of the proposed algorithms compared to other metaheuristic proposed in the literature. The computational results shown that, the proposed sexual selection and FGAs are competitive and capable of generating near optimal solutions.