[[PageOutline]] = Samples = This section provides additional sample files for the HeuristicLab 3.3 Optimizer some of which are included as demo samples in the Optimizer. == Travelling Salesman == * [#GATSP Genetic Algorithm - TSP]: A genetic algorithm which solves rge "ch130" travelling salesman problem (imported from TSPLIB) * [#IslandGA Island Genetic Algorithm - TSP]: An island genetic algorithm which solves the "ch130" traveling salesman problem (imported from TSPLIB) * [#TSTSP Tabu Search - TSP]: A tabu search algorithm that solves the "ch130" TSP (imported from TSPLIB) ---- [=#GATSP] === Genetic Algorithm - TSP === This sample demonstrates how to employ a genetic algorithm to optimize a travelling salesman problem instance, namely "ch130" from the [http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ TSP Lib]. '''Algorithm:''' [[Genetic Algorithm]] '''Algorithm Parameters:''' * !PopulationSize: 100 * Elites: 1 * !MutationProbability: 5% * !MaximumGenerations: 1000 * Selector: !ProportionalSelector * Crossover: Crossover2 (cf. Affenzeller, M. et al. 2009. Genetic Algorithms and Genetic Programming - Modern Concepts and Practical Applications. CRC Press. p. 135) * Mutator: !InversionManipulator '''Problem:''' [[Travelling Salesman Problem]] '''Problem Parameters:''' * !BestKnownQuality: 6110 * !BestKnownSolution: The best known solution of this TSP instance (cf. TSP Lib) * Coordinates: The x and y coordinates of the cities * !DistanceMatrix: null * Evaluator: [[Travelling Salesman Problem#Evaluator| TSPRoundedEuclideanPathEvaluator]] * Maximization: False * !SolutionCreator: !RandomPermutationCreator * !UseDistanceMatrix: True ---- [=#IslandGA] === Island Genentic Algorithm - TSP === '''Algorithm:''' [[IslandGA| Island Genetic Algorithm]] '''Algorithm Parameters:''' * Analyzer: !MultiAnalyzer * Crossover: !OrderCrossover2 * Elites: 1 * !EmigrantsSelector: !BestSelector * !ImmigrationReplacer: !WorstReplacer * !IslandAnalyzer: !MultiAnalyzer * !MaximumGenerations: 1000 * !MigrationInterval: 50 * !MigrationRate: 25% * Migrator: !UnidirectionalRingMigrator * !MutationProbability: 5% * Mutator: !InversionManipulator * !NumberOfIslands: 5 * !PopulationSize: 100 * Seed: - * Selector: !ProportionalSelector * !SetSeedRandomly: True '''Problem:''' [[Travelling Salesman Problem]] '''Problem Parameters:''' * !BestKnownQuality: 6110 * !BestKnownSolution: The best known solution of this TSP instance (cf. TSP Lib) * Coordinates: The x and y coordinates of the cities * !DistanceMatrix: null * Evaluator: !TSPRoundedEuclideanPathEvaluator * Maximization: False * !SolutionCreator: !RandomPermutationCreator * !UseDistanceMatrix: True ---- [=#TSTSP] === Tabu Search - TSP === '''Algorithm:''' [[TS| Tabu Search]] '''Algorithm Parameters:''' * Analyzer: !MultiAnalyzer * !MaximumIterations: 1000 * !MoveEvaluator: TSPInversionMoveRoundedEuclideanPathEvaluator * !MoveGenerator: !StochasticInversionMultiMoveGenerator * !MoveMaker: !InversionMoveMaker * !SampleSize: 500 * Seed: - * !SetSeedRandomly: True * !TabuChecker: !InversionMoveSoftTabuCriterion * !TabuMaker: !InversionMoveTabuMaker * !TabuTenure: 60 '''Problem:''' [[Travelling Salesman Problem]] '''Problem Parameters:''' * !BestKnownQuality: 6110 * !BestKnownSolution: The best known solution of this TSP instance (cf. TSP Lib) * Coordinates: The x and y coordinates of the cities * !DistanceMatrix: null * Evaluator: TSPRoundedEuclideanPathEvaluator * Maximization: False * !SolutionCreator: !RandomPermutationCreator * !UseDistanceMatrix: True ---- == Real-valued Test Functions == * [#ESGriewank Evolution Strategy - Griewank]: An evolution strategy which solves the 10-dimensional Griewank test function * [#SARastrigin Simulated Annealing - Rastrigin]: A simulated annealing algorithm that solves the 2-dimensional Rastrigin test function ---- [=#ESGriewank] === Evolution Strategy - Griewank === A pre-defined evolution strategy which solves the 10-dimensional [TestFunctions#GriewankFunction Griewank test function]. HeuristicLab 3 provides a set of real valued test functions for benchmarking purposes. For a full overview please go the [TestFunctions Test Functions] wiki page. '''Algorithm:''' [[Evolution Strategy]] '''Algorithm Parameters:''' * Population Size: 20 * Children: 500 * !MaximumGenerations: 200 * !ParentsPerChild: 5 * !PlusSelection: False (Comma Selection) * Recombinator: !AverageCrossover * Mutator: !NormalAllPositionsManipulator '''Problem:''' [[Single Objective Test Function]] '''Problem Parameters:''' * !BestKnownQuality: 0 * !BestKnownSolution: [0;0;0;0;0;0;0;0;0;0] * Bounds: [-600, 600] * Evaluator: !GriewankEvaluator * Maximization: False * !ProblemSize: 10 * !SolutionCreator: !UniformRandomRealVectorCreator ---- [=#SARastrigin] === Simulated Annealing - Rastrigin === '''Algorithm:''' [[SA| Simulated Annealing]] '''Algorithm Parameters:''' * Analyzer: !MultiAnalyzer * !AnnealingOperator: !ExponentialDiscreteDoubleValueModifier * !EndTemperature: 1E-06 * !InnerIterations: 50 * !MaximumIterations: 1000 * !MoveEvaluator: !RastriginAdditiveMoveEvaluator * !MoveGenerator: !StochasticNormalMultiMoveGenerator * !MoveMaker: !AdditiveMoveMaker * Seed: - * !SetSeedRandomly: True * !StartTemperature: 1 '''Problem:''' [[Single Objective Test Function]] '''Problem Parameters:''' * !BestKnownQuality: 0 * !BestKnownSolution: [0;0] * Bounds: ([-5, 12], [-5,12]) * Evaluator: !RastriginEvaluator * Maximization: False * !ProblemSize: 2 * !SolutionCreator: !UniformRandomRealVectorCreator ---- == Genetic Programming == * [#GPArtificialAnt Genetic Programming - Artificial Ant Problem]: A standard genetic programming algorithm to solve an artificial ant problem (Santa-Fe ant trail) * [#GPSymbolicRegressionBostonHousing Genetic Programming - Symbolic Regression (Boston Housing)]: A standard genetic programming algorithm to solve a symbolic regression problem (Boston Housing dataset) * [#GPSymbolicRegressionTower Genetic Programming - Symbolic Regression (Tower)]: A genetic programming algorithm to solve a symbolic regression problem (Tower dataset) * [#GPSymbolicRegressionMackeyGlass Genetic Programming - Symbolic Regression (Mackey-Glass)]: A genetic programming algorithm to create a one-step prediction model for a chaotic time series (Mackey-Glass time series) * [#GPSymbolicClassificationWisconsin Genetic Programming - Symbolic Classification (Wisconsin)]: A genetic programming algorithm to solve a symbolic classification problem (Wisconsin Diagnostic Breast Cancer dataset) * [#GPSymbolicClassificationMammography Genetic Programming - Symbolic Classification (Mammography)]: A genetic programming algorithm to solve a symbolic classification problem (Mammography dataset) * [#GPBooleanEvenParity4 Genetic Programming - Even Parity (4 inputs)]: A genetic programming algorithm to synthesize the boolean even parity function with 4 binary inputs * [#GPBooleanMultiplexer11 Genetic Programming - Multiplexer (11 inputs)]: A genetic programming algorithm to synthesize the boolean multiplexer function with 11 binary inputs ---- [=#GPArtificialAnt] === Genetic programming - Artificial Ant Problem === [attachment:SGP_SantaFe.hl] [[Image(SantaFe Result.png, width=500, right, margin-right=30, margin-left=30)]] '''Algorithm:''' [[Genetic Algorithm]] '''Algorithm Parameters:''' * Analyzer: !MultiAnalyzer * Crossover: !SubtreeCrossover - An operator which performs subtree swapping crossover * Elites: 1 * !MaximumGenerations: 100 * !MutationProbability: 15% * Mutator: !MultiSymbolicExpressionTreeManipulator * Population Size: 500 * Seed: - * Selector: !TournamentSelector * !SetSeedRandomly: True '''Problem:''' [[Artificial Ant Problem]] '''Problem Parameters:''' * !ArtificialAntExpressionGrammar: !IfFoodAhead, Prog2, Prog3, Right, Left, Move * !BestKnownQuality: 89 * Evaluator: !ArtificialAntEvaluator * !MaxExpressionDepth: 6 * !MaxExpressionLength: 50 * !MaxFunctionArguments: 3 * !MaxFunctionDefinitions: 3 * Maximization: True * !MaxTimeSteps: 600 * !SolutionCreator: !ProbabilisticTreeCreator * World: 32x32 grid, 89 randomly scattered food items ---- [=#GPSymbolicRegressionBostonHousing] === Genetic programming - Symbolic Regression (Boston Housing)=== [attachment:SGP_SymbReg-Boston-Housing.hl] Example for a simple genetic programming algorithm to create a regression model for the estimation of the median value of houses in a certain in the Boston area based on other parameters of that region. The original dataset was downloaded from http://archive.ics.uci.edu/ml/datasets/Housing. '''Algorithm:''' [[Genetic Algorithm]] '''Algorithm Parameters:''' '''Problem:''' [[Symbolic Regression Problem]] '''Problem Parameters:''' * !BestKnownQuality: null * !DataAnalysisProblemData: Data imported from Housing Dataset from UCI Repository (cf. http://archive.ics.uci.edu/ml/datasets/Housing) * Evaluator: !SymbolicRegressionScaledMeanSquaredErrorEvaluator * !FunctionTreeGrammar: Addition, Subtraction, Multiplication, Division, Constant, Variable * !LowerEstimationLimit: -289,08968253968254 * !MaxExpressionDepth: 10 * !MaxExpressionLength: 100 * !MaxFunctionArguments: 0 * !MaxFunctionDefiningBranches: 0 * Maximization: False * !SolutionCreator: !ProbabilisticTreeCreator * !SymbolicExpressionTreeInterpreter: - * !UpperEstimationLimit: 332,91031746031746 ---- [=#GPSymbolicRegressionTower] === Genetic programming - Symbolic Regression (Tower)=== [attachment:SGP_SymbReg.hl] Example for a simple genetic programming algorithm to create a regression model for the estimation of a product quality parameter in an industrial chemical process. The original dataset was downloaded from http://vanillamodeling.com/realproblems.html. * Population size: 500 * Generations: 100 * Tournament selection: group size=7 * Mutation rate: 15% * Function set: +, *, -, /, average, log, power, root, exponential * Terminal set: constants, x01, x02, x03, x04, x05, x06, x08, x09, x10, x12, x14, x15, x17, x18, x19, x20, x22, x23, x24 * Fitness function: R² of predicted and original tower response ---- [=#GPSymbolicRegressionMackeyGlass] === Genetic programming - Symbolic Regression (Mackey-Glass)=== [attachment:SGP_SymbReg-Mackey-Glass.hl] Example for a simple genetic programming algorithm to create a dynamic model for the one-step prediction of the chaotic Mackey Glass (T=17) time series. The original dataset was downloaded from http://www.bme.ogi.edu/~ericwan/data.html. * Population size: 500 * Generations: 100 * Tournament selection: group size=7 * Mutation rate: 15% * Function set: +, *, -, /, average, log, power, root, exponential * Terminal set: constants, x(t-90) .. x(t-1) * Fitness function: R²(xPred(t), xOrig(t)) ---- [=#GPSymbolicClassificationWisconsin] === Genetic programming - Symbolic Classification (Wisconsin)=== [attachment:SGP_Classification-WDPC.hl] Example for a simple genetic programming algorithm to create a classification model for the estimation of malignant or benign tumor diagnosis based on features extracted through analysis of tumorous cells in a tissue sample. The original dataset was downloaded from the UCI Machine Learning Repository (http://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+(Diagnostic)). The algorithm uses all available GP manipulation operators, single-point cross-over and squared Pearson's correlation coefficient evaluation. The algorithm reaches an accuracy of ~95% on the test set. This algorithm is supposed to be a demo for GP in HeuristicLab, the aim is not to find high quality models. ---- [=#GPSymbolicRegressionMammography] === Genetic programming - Symbolic Classification (Mammography)=== [attachment:SGP_SymbClass_Mammographic.hl] A genetic programming algorithm to create a classification model for the prediction of malignant or benign tumor diagnosis based on features extracted through a non-invasive mammography breast cancer screening. Original dataset stems from the UCI Machine Learning Repository (http://archive.ics.uci.edu/ml/datasets/Mammographic+Mass). ---- [=#GPBooleanEvenParity4] === Genetic Programming - Even Parity (4 inputs) === [attachment:SGP_Boolean-Even-Parity-4.hl] A genetic programming algorithm to synthesize the boolean even parity function with 4 binary inputs * Population size: 4000 * Generations: 100 * Function set: AND, OR, NOT * Terminal set: D0, D1, D2, D3 * Max. function defining branches: 3 * Max. function arguments: 3 Up to three automatically defined functions (ADF), each with up to three arguments, are allowed. ==== References ==== John R. Koza, Genetic Programming - On the Programming of Computers by Means of Natural Selection, MIT Press, 1992 ---- [=#GPBooleanMultiplexer11] === Genetic Programming - Multiplexer (11 inputs) === [attachment:SGP_Boolean-Multiplexer-11.hl] A genetic programming algorithm to synthesize the boolean multiplexer function with 11 binary inputs * Population size: 4000 * Generations: 100 * Function set: IF, AND, OR, NOT * Terminal set: A0, A1, A2, D0, D1, D2, D3, D4, D5, D6, D7 ==== References ==== John R. Koza, Genetic Programming - On the Programming of Computers by Means of Natural Selection, MIT Press, 1992 ---- == Additional == * [#LSKnapsack Local Search - Knapsack]: A local search algorithm that solves a randomly generated Knapsack problem ---- [=#LSKnapsack] === Local Search - Knapsack === '''Algorithm:''' [[LocalSearch| Local Search]] '''Algorithm Parameters:''' * Analyzer: !MultiAnalyzer * !MaximumIterations: 1000 * !MoveEvaluator: !KnapsackOneBitflipMoveEvaluator * !MoveGenerator: !ExhaustiveBitflipMoveGenerator * !MoveMaker: !OneBitflipMoveMaker * !SampleSize: 100 * Seed: - * !SetSeedRandomly: True '''Problem:''' [[Knapsack Problem]] '''Problem Parameters:''' * !BestKnownQuality: 226 * !BestKnownSolution: Binary Vector * Evaluator: !KnapsackEvaluator * !KnapsackCapacity: 134 * Maximization: True * Penalty: 1 * !SolutionCreator: !RandomBinaryVectorCreator * Values: The values of the items. * Weights: The weights of the items.