% /*M-FILE SCRIPT SGALAB_contents MMM SGALAB */ %
% % /*==================================================================================================
% Simple Genetic Algorithm Laboratory Toolbox for Matlab 7.x
%
% Copyright 2007 The SxLAB Family - Yi Chen - chenyi2005@gmail.com
% ====================================================================================================
%File description:
% this is the content m file for SGALAB
% I try to do my best to improve SGALAB's CFRUP, where
% CFURP is function's QA Std.
% C-- Consistency
% F-- Functionality
% U-- Usability
% R-- Reliability
% P-- Performance
%===================================================================================================
%Revision -
%Date Name Description of Change email Location
%29-Sep-2006 Chen Yi Initial version chenyi2005@gmail.com Shanghai
%30-May-2007 Chen Yi Beta5002 chenyi2005@gmail.com Glasgow
%HISTORY$
%==================================================================================================*/
% SGALAB_contents Begin
SGALAB_Toolbox_List = list_current_dir_files
%%Entry function
% SGA_entry -- entry for math optimization
% SGA_entry_TSP -- entry for TSP case
%% SGA_about
%% Encoding/Decoding method
%%(1) binary encoding
% SGA__binary_encoding
% SGA__binary_decoding
% SGA__binary_uniformly_encoding -- uniformly distributed random integers
% SGA__binary_manually_encoding -- binary coding designed or given by user
% SGA__get_distance_hamming -- to get hamming distance between 2 vectors, encoding space, genotypic space
% SGA__get_distance_combined -- combined distance both genotypic and phenotypic space
% SGA__get_distance_phenotypic -- to get phenotypic distance, fitness space
% SGA_FITNESS_sharing -- to get shared fitness
%%(2)real encoding (float type)
% SGA__real_encoding -- we use rand() to Generate matrix of uniformly distributed random integers
% SGA__real_decoding -- float decoding
% SGA__real_roulettewheel_selection
%%(3) int encoding
% SGA__int_uniformly_encoding
% SGA__int_decoding
%%(4)Gray code
% SGA__gray_encoding
% SGA__gray_decoding
%%(5)messy code
% SGA__messy_encoding
% SGA_cut
% SGA_splice
%%(6)DNA code
%%(7)TSP path generation
% SGA__permutation_encoding
% SGA__TSP_xypoint_to_costmatrix
%%Selection
%%(1)roulette wheel selection
% SGA__roulettewheel_selection
%%(2)stochastic universal sampling
% SGA__selection_stochastic
%%(3)local selection
%%(4)truncation selection
% SGA__selection_truncation
%%(5)tournament selection
% SGA__selection_tournament
%%(6)uniform random selection
% SGA__selection_uniform_random
%%Crossover
%%(1) real valued recombination
% SGA__crossover_real_int_singlepoint
%% (1-1) discrete recombination
%% (1-2) intermediate recombination
%% (1-3) linear recombination
%% (1-4) extended linear recombination
%%(2)binary valued crossover
%%(2-1)single-point crossover
% SGA__binary_singlepoint_crossover
%%(2-2)multiple-point crossover
%%(2-3)uniform crossover
%%(2-4)shuffle crossover
%%(2-5)crossover with reduced surrogate
%%(3)TSP Crossover
% SGA__TSP_PMX_crossover - TSP - Partially Matched Crossover, PMX
% SGA__TSP_OX_crossover - TSP - Ordered Crossover operation, OX
% SGA__TSP_CX_crossover - TSP - Cycle Crossover, CX
% SGA__TSP_BOOLMATRIX_crossover - TSP - Matrix Representations and Operators
% SGA__TSP_EAX_crossover - Travel Salesman Problem--TSP Operator
% Edge Assembly Crossover( EAX ) is to do
% Edge Recombination Crossover(ERX) With double edge marker,
% Briefly:
% EAX = ERX + Edge_Marker
% SGA__TSP_topological_crossover-Topological Crossover for the Permutation Representation
Alternating Position Crossover (AP) (1999)Larranaga, Kuijpers, Poza, Murga
% SGA__TSP_CX_crossover Cycle Crossover (CX) (1987) Oliver, Smith and Holland
Distance Preserving Crossover (DPX) (1996) Freisbein and Merz
% SGA__TSP_EAX_crossover Edge Assembly Crossover (EAX) (1997) Nagata and Kobayashi
Edge Recombination Crossover (ER) (1989) Whitley, Timothy, Fuquay
Heuristic Crossover (HEU) (1987) Grefenstette
Inver-over Operator (IOO) (1998) Tao and Michalewicz
Maximal Preservative Crossover (MPX) (1988) Mühlenbein, Schleuter and Kr?mer
Position Based Crossover (POS) (1991) Syswerda
% SGA__TSP_OX_crossover Order Crossover (OX1) (1985) Davis
Order Based Crossover (OX2) (1991) Syswerda
% SGA__TSP_PMX_crossover Partially mapped Crossover (PMX) (1985) Goldberg and Lingle
Voting Recombination Crossover (VR) (1989) Mühlenbein
%%Mutation method
% SGA__binary_singlepoint_mutation
% SGA__TSP_displacement_mutation Displacement Mutation (DM) (1992) Michalewicz
% SGA__TSP_ReciprocalExchange_mutation Exchange Mutation (EM) (1990) Banzhaf
% SGA__TSP_insertion_mutation Insertion Mutation (ISM) (1988) Fogel
% SGA__TSP_inversion_mutation Inversion Mutation (IVM) (1990) Fogel
Scramble Mutation (SM) (1991) Syswerda
Simple Inversion Mutation (SIM) (1975) Holland
%%TSP Mutation
% SGA__TSP_inversion_mutation (Inversion. Select two points along the permutation, cut it at these points and re-insert the reversed string.
% (1 2 | 3 4 5 6 | 7 8 9) ? (1 2 | 6 5 4 3 | 7 8 9).)
% SGA__TSP_insertion_mutation (Insertion. Select a city and insert it in a random place.)
% SGA__TSP_displacement_mutation ( Displacement. Select a subtour and insert it in a random place.)
% SGA__TSP_ReciprocalExchange_mutation (Reciprocal Exchange. Swap two cities.)
%%Fitness Assignment
% SGA_FITNESS_assignment -- make fitness assignment by the following 2 functions
% SGA_FITNESS_scaling -- Proportional fitness assignment
% (1) linear scaling : f' = alpha*f + beta
% (2) Power scaling : f' = power(f,Kpara)
% (3) Exponential_function - Boltzmann scaling'
% f' = exp(-Kpara*f)
% (4) Normalizing scaling: f' = ( f - fmin + gamma )/( fmax - fmin + gamma );
% SGA_FITNESS_rank -- Rank-based fitness assignment
% SGA_TSP_cost_evaluating -- is to evaluate fitness from TSP cost
% SGA_TSP_FITNESS_function
% SGA_CONSFUNC_evaluating
% SGA_CONSFUNC_function
% SGA_TSP_FITNESS_evaluating
%% Multi-Objective Algorithms
% % The 1st generation: Vector Evaluation approach
% Vector Evaluated Genetic Algorithm (veGA: Schaffer, 1985)
% Schaffer, J. D.: “Multiple objective optimization with vector evaluated genetic algorithms”, Proc. of 1st Inter. Conf. on GAs and Their Applic., pp.93-100, 1985.
% % The 2nd generation: Pareto ranking + Diversity
% Multiobjective Genetic Algorithm (moGA: Fonseca and Fleming, 1993)
% Fonseca, C. M. & P. J. Fleming: “Genetic algorithms for multiobjective optimization: formulation, discussion and generalization”, Proc. of the 5th Inter. Conf. on GAs, pp. 416-423, 1993.
% Non-dominated Sorting Genetic Algorithm (nsGA: Deb, 1995)
% Srinivas, N. & K. Deb: “Multiobjective function optimization using nondominated sorting genetic algorithms”, Evolutionary Computation, vol. 3, pp. 221-248, 1995.
% % The 3rd generation: Weighted Sum + Elitist Preserve
% Random-weight Genetic Algorithm (rwGA: Ishibuchi et al., 1998)
% Ishibuchi, H & T. Murata: “A multiobjective genetic local search algorithm and its application to flowshop scheduling”, IEEE Trans. on Sys., Man & Cyber., vol. 28, no. 3, pp. 392-403, 1998.
% Strength Pareto Evolutionary Algorithm (spEA: E. Zitzler et al., 1999)
% Zitzler, E. & L. Thiele: “Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach”, IEEE Trans. on Evolutionary Comput., vol.3, no.4, pp.257-271, 1999.
% Adaptive-weight Genetic Algorithm (awGA: Gen and Cheng, 2000)
% Gen, M. & R. Cheng: Genetic Algorithms and Engineering Optimization, John Wiley & Sons, New York, 2000.
% Non-dominated Sorting Genetic Algorithm Ⅱ (nsGAⅡ: Deb, 2002)
% Deb, K., A. Pratap, S. Agarwal & T. Meyarivan: “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-Ⅱ.” IEEE Trans. on Evolutionary Comput., vol. 6, no. 2, pp.182-197, 2002
% Non-dominated Sorting Genetic Algorithm (nsGA: Deb, 1995)
% Srinivas, N. & K. Deb: “Multiobjective function optimization using nondominated sorting genetic algorithms”, Evolutionary Computation, vol. 3, pp. 221-248, 1995.
%%Existing literature seems to approach this ranking problem using methods that can be classified in one of three
%%ways:
%% [1] the aggregating approaches,
%% No. SGALAB Function Type Reference
% 1) SGA__MO_AGG_SWO_fitness() weighted sum approach,
% 2) SGA__MO_AGG_EC_fitness() constraint method,
% 3) SGA__MO_AGG_GP_fitness() goal programming.
%% [2] the non-Pareto approaches and
%% No. SGALAB Function Type Reference
% 1) SGA__MO_NON_Pareto_VEGA VEGA Schaffer(1984) SGALAB_MO_VEGA_DEMO.m is a demo for VEGA
%% [3] the Pareto approaches.
% Pareto ranking
% SGA__pareto_ranking -- ranking fitness by Goldberg's method
% options :
% 'Goldberg','G' -- Goldberg's method: rank = rank + 1;
% 'Fonceca','Fleming','MO','F' -- Fonceca and Fleming's ranking method
% current rank = the number of its dominating individulas + 1
%% No. Type SGALAB Function Reference
% 1st Generation of Multi-Objective GAs
% 2) MOGA SGA__MO_Pareto_MOGA Fonseca and Fleming(1993)
% 3) NPGA SGA__MO_Pareto_NPGA Horn,Nafpliotis,Goldberg(1994)
% 4) NSAG SGA__MO_Pareto_NSGA Srinivas and Deb(1994)
% 2nd Generation of Multi-Objective GAs
5) SPEA SGA__MO_Pareto_SPEA Zitzler and Thiele(1999)
6) ELSA SGA__MO_Pareto_ELSA Menczer,Degeratu,Street(2000)
7) IEDS SGA__MO_Pareto_IEDS Parmee,Cvetkovic,Watson,Bonham(2000)
8) MOMGA SGA__MO_Pareto_MOMGA Van Veldhuizen and Lamont(2000b)
%9) NSGA-II SGA__MO_Pareto_NSGA Deb,Agrawal,Pratab,Meyarivan(2000)
10) PAES SGA__MO_Pareto_PAES Knowles and Corne(2000)
11) MOMGA-II SGA__MO_Pareto_MOMGA Zydallis, Van Veldhuizen, Lamont(2001)
12) PDE SGA__MO_Pareto_PDE Abbass,Sarker,Newton(2001)/Abbass,Sarker(2002)
13) MPANN SGA__MO_Pareto_MPANN Abbass(2001;2002a)
14) SPEA2 SGA__MO_Pareto_SPEA2 Zitzler,Laumanns,Thiele(2001)
15) PCGA SGA__MO_Pareto_PCGA Kumar and Rockett(2002)
16) SPDE SGA__MO_Pareto_SPDE Abbass(2002b)
%% Hybrid Algorithm , GA + Other Intelligent Algorithms
%% ( 1 ) GA + Fuzzy
%% ( 2 ) GA + ANN
% SGALAB_contents End
