Fuzzy genetic algorithms for combinatorial optimisation problems
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 t...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2012
|
| Subjects: | |
| Online Access: | http://psasir.upm.edu.my/id/eprint/32238/1/IPM%202012%201R.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| id |
my-upm-ir.32238 |
|---|---|
| record_format |
uketd_dc |
| spelling |
my-upm-ir.322382015-01-15T01:46:55Z Fuzzy genetic algorithms for combinatorial optimisation problems 2012-03 Varnamkhasti, Mohammad Jalali 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. Genetic algorithms Combinatorial optimization 2012-03 Thesis http://psasir.upm.edu.my/id/eprint/32238/ http://psasir.upm.edu.my/id/eprint/32238/1/IPM%202012%201R.pdf application/pdf en public phd doctoral Universiti Putra Malaysia Genetic algorithms Combinatorial optimization Institute for Mathematical Research |
| institution |
Universiti Putra Malaysia |
| collection |
PSAS Institutional Repository |
| language |
English |
| topic |
Genetic algorithms Combinatorial optimization |
| spellingShingle |
Genetic algorithms Combinatorial optimization Varnamkhasti, Mohammad Jalali Fuzzy genetic algorithms for combinatorial optimisation problems |
| description |
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. |
| format |
Thesis |
| qualification_name |
Doctor of Philosophy (PhD.) |
| qualification_level |
Doctorate |
| author |
Varnamkhasti, Mohammad Jalali |
| author_facet |
Varnamkhasti, Mohammad Jalali |
| author_sort |
Varnamkhasti, Mohammad Jalali |
| title |
Fuzzy genetic algorithms for combinatorial optimisation problems |
| title_short |
Fuzzy genetic algorithms for combinatorial optimisation problems |
| title_full |
Fuzzy genetic algorithms for combinatorial optimisation problems |
| title_fullStr |
Fuzzy genetic algorithms for combinatorial optimisation problems |
| title_full_unstemmed |
Fuzzy genetic algorithms for combinatorial optimisation problems |
| title_sort |
fuzzy genetic algorithms for combinatorial optimisation problems |
| granting_institution |
Universiti Putra Malaysia |
| granting_department |
Institute for Mathematical Research |
| publishDate |
2012 |
| url |
http://psasir.upm.edu.my/id/eprint/32238/1/IPM%202012%201R.pdf |
| _version_ |
1747811653558206464 |