Recent posts (max 10) - Browse or Archive for more

Modeling scheduling problems with HeuristicLab

HeuristicLab makes it very easy to model scheduling problems. HeuristicLab comes included with the simulation framework Sim#, a port of SimPy to C#. With Sim# writing process-based simulation models requires little effort. Here, I demonstrate in only a few lines of code how to implement a permutation flow shop problem using a Programmable Problem (single-objective). You can create this problem in the GUI from the New Item dialog and paste following code into the editor pane, then hit compile. You can optimize solutions after you dragged it to the Problem tab of an algorithm that can handle programmable permutation-based problems (e.g. Genetic Algorithm).

using System;
using System.Linq;
using System.Collections.Generic;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Optimization;
using IRandom = HeuristicLab.Core.IRandom;
using SimSharp;
using SysEnv = System.Environment;
using SimEnv = SimSharp.Environment;

namespace HeuristicLab.Problems.Programmable {
  public class FlowShopProblemDefinition : CompiledProblemDefinition,
                                           ISingleObjectiveProblemDefinition {
    private static readonly string[] machineSep = new [] { SysEnv.NewLine };
    private static readonly string[] jobSep = new [] { " ", "\t" };
    // from http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/flowshop.dir/tai20_5.txt
    private static readonly string instance = @"
 54 83 15 71 77 36 53 38 27 87 76 91 14 29 12 77 32 87 68 94
 79  3 11 99 56 70 99 60  5 56  3 61 73 75 47 14 21 86  5 77
 16 89 49 15 89 45 60 23 57 64  7  1 63 41 63 47 26 75 77 40
 66 58 31 68 78 91 13 59 49 85 85  9 39 41 56 40 54 77 51 31
 58 56 20 85 53 35 53 41 69 13 86 72  8 49 47 87 58 18 68 28
";
    private int M, J; // number of machines, jobs
    private List<List<int>> pij; // processing times per machine, job
    
    // objective is to minimize makespan
    public bool Maximization { get { return false; } }

    public override void Initialize() {
      // processing times are parsed from the instance
      pij = instance.Split(machineSep, StringSplitOptions.RemoveEmptyEntries)
              .Select(x => x.Split(jobSep, StringSplitOptions.RemoveEmptyEntries)
                            .Select(y => int.Parse(y)).ToList()).ToList();
      M = pij.Count;
      J = pij[0].Count;
      // encoding is created
      Encoding = new PermutationEncoding("p", length: J,
                                         type: PermutationTypes.Absolute);
    }

    public double Evaluate(Individual ind, IRandom random) {
      // create a new Sim# environment
      var env = new SimEnv();
      // create the M machines
      var machines = Enumerable.Range(0, M).Select(x => new Resource(env)).ToArray();
      // add the jobs in order given by the permutation
      foreach (var o in ind.Permutation("p"))
        env.Process(Job(env, o, machines));
      // run the simulation
      env.Run();
      // return the current simulation time (last finish time)
      return env.NowD;
    }
    
    private IEnumerable<Event> Job(SimEnv env, int j, Resource[] machines) {
      // for each of the M machines in order from 0 to M-1
      for (var m = 0; m < M; m++) {
        // create a new request for the next machine
        // the machine is freed after the using block
        using (var req = machines[m].Request()) {
          // wait upon obtaining the machine
          yield return req;
          // process the job j on machine m
          yield return env.TimeoutD(pij[m][j]);
        }
      }
    }

    public void Analyze(Individual[] individuals, double[] qualities,
                        ResultCollection results, IRandom random) { }
    
    // for move-based algorithms, all possible swap2 neighbors are returned
    public IEnumerable<Individual> GetNeighbors(Individual ind, IRandom random) {
      var p = ind.Permutation("p");
      foreach (var move in ExhaustiveSwap2MoveGenerator.Apply(p)) {
        var neighbor = ind.Copy();
        var perm = neighbor.Permutation("p");
        Swap2Manipulator.Apply(perm, move.Index1, move.Index2);
        yield return neighbor;
      }
    }
  }
}

This includes a "simple" 5 machine / 20 job problem instance from Taillard's instances.

HeuristicLab 3.3.14 "Denver" Release

We are happy to announce the release of HeuristicLab 3.3.14, which we finished at this year's Genetic and Evolutionary Computation Conference (GECCO) in Denver, CO, USA.

HeuristicLab 3.3.14 "Denver" contains the following new features:

  • New problems:
    • Bin Packing
    • Probabilistic TSP
    • Multi-Objective Testfunctions
  • New data analysis algorithms:
    • Gradient Boosted Regression
    • Nonlinear Regression
    • Elastic-Net
  • Gradient Charts

For a full list of all changes have a look at the ChangeLog.

Go to the Download page or click on the image below to get HeuristicLab 3.3.14 "Denver" now!

Run-Length Distribution Analysis with HeuristicLab

We have included in our trunk today new analyzers for measuring algorithm performance. The analyzers are called QualityPerEvaluationsAnalyzer and QualityPerClockAnalyzer. They record the convergence graph in each run and add it as a result. A new run analyzer called "Run-length Distribution View" can be used to build, so called, ECDFs out of the convergence graphs in the individual runs using a single or multiple targets. This allows plotting the cumulative success probability of reaching a certain fitness value given a certain effort (measured in evaluated solutions or elapsed wall-clock time). These plots can be used to compare the run-length distributions of algorithm instances applied to one or many problem instances.

Run-Length Distribution of Algorithm Instances on the esc32a QAP Instance

The run-length distribution view can cope with runs of different length such that it would not simple plot the number of hits divided by the total number of runs in the experiment. Instead, the denominator is decreased whenever a run missed the target and terminated prematurly. Thus one can use shorter runs to obtain more accurate ECDFs for lower amounts of function evaluations. In order to visualize missed runs, we plot a shaded area for every curve that represents the min and max bounds for the ECDF. The minimum level is pessimistic and assumes that all prematurely missed runs would have not hit the target later on. The upper level is optimistic and assumes that all prematurely missed runs would have immediately found the target right afterwards. The line that is based purely on the observed hits is thus in-between these two.

Run-Length Distribution of a Genetic Algorithm Instance applied to the berlin52 TSP Instance

Together with the other run analyzers this one provides another means for algorithm developers to test and compare their instances. Currently, this feature is part of the main development trunk.

HeuristicLab 3.3.13 "Windischgarsten" Release

Right before our annual HeuristicLab retreat (this time in Windischgarsten, Austria), we are proud to announce the release of HeuristicLab 3.3.13 "Windischgarsten" with the following new features:

  • New Algorithms:
    • Age-layered Population Structure (ALPS)
    • Offspring Selection Evolution Strategy (OSES)
  • New Problems:
    • Multi-objective external evaluation problem
    • Gentic programming for code generation (Robocode)
    • Further genetic programming problems: Even Parity, Multiplexer, Koza-style symbolic regression
  • Additional accuracy metrics for classification models (and comparison to baseline algorithms)
  • Quantile Regression based on Gradient Boosted Trees
  • Mathematica export for symbolic regression/classification solutions
  • Improved complexity measures for multi-objective symbolic regression
  • Improved persistence of data-analysis models (SVM, Gaussian Process, GBT, Random Forest)
  • Hive Statistics: A new WebApp that shows information about running jobs and available resources in HeuristicLab Hive

For a full list of all changes have a look at the ChangeLog. Go to the Download page or click on the image below to get HeuristicLab 3.3.13 "Windischgarsten" now!

In memoriam John H. Holland 1929-2015

We're sorry to hear that the inventor of the genetic algorithm, John H. Holland, has passed away at 86. He was a pioneer in the study of complex adaptive systems and an inspirational source for many researchers including our research group. The importance of his work cannot be emphasized enough and it will certainly continue to influence generations of researchers that are yet to come.

santafe.edu

  • Posted: 2015-08-11 15:42
  • Author: abeham
  • Categories: (none)
  • Comments (0)

HeuristicLab 3.3.12 "Madrid" Release

Following our conference-oriented release schedule, we are happy to announce the release of HeuristicLab 3.3.12 "Madrid" from this year's Genetic and Evolutionary Computation Conference (GECCO).

HeuristicLab 3.3.12 "Madrid" contains the following new features:

  • New problem: NK[P,Q] landscapes
  • New problem: Orienteering
  • New encoding: Linear linkage
  • New data analysis algorithm: Gradient boosted trees
  • New optimizer: TimeLimitRun limits algorithm execution by wall-clock time and can take snapshots at predefined points
  • Integration of the Sim# simulation framework as external library (Sim# at GitHub)
  • Hive status page is replaced by a modular WebApp
  • Improved and searchable "New Item" dialogue
  • C# code formatter for symbolic regression/classification
  • The symbolic expression tree encoding can now be used with Programmable/Basic problems
  • Kernel density estimation for the histogram control

For a full list of all changes have a look at the ChangeLog. Go to the Download page or click on the image below to get HeuristicLab 3.3.12 "Madrid" now!

HeuristicLab 3.3.11 "Beach Bar" Release

As with every EuroCAST conference, the HeuristicLab development team is proud to announce the release of HeuristicLab 3.3.11 "Beach Bar".

Among others, HeuristicLab 3.3.11 "Beach Bar" contains the following new features:

  • New algorithm: parameter-less population pyramid (P3). Thanks to Brian Goldman from the BEACON Center for the Study of Evolution in Action.
  • New binary test problems:
    • Deceptive trap problem
    • Deceptive trap step problem
    • HIFF problem
  • New views for statistical testing and analysis of run collections
  • New UI for C# scripts based on AvalonEdit
  • New problem type: Programmable problem
  • New APIs that make it easier to implement algorithms and problems
  • Upgraded to .NET 4.5

For a full list of all changes in HeuristicLab 3.3.11 "Beach Bar" have a look at the ChangeLog.

Go to the Download page or click on the image below to get HeuristicLab 3.3.11 "Beach Bar" now!

HeuristicLab moves to .NET 4.5

After staying on the .NET 4 platform for 4 years we have decided to upgrade to .NET 4.5. At the moment this only affects the trunk version of HL, but in the future also the stable branch and the next release (3.3.11) will be built on .NET 4.5. The main reason for this decision is that we are going to use new features from .NET 4.5 (async/await and System.IO.Compression.ZipArchive).

For you as a user or developer this means the following:

  • Running HeuristicLab now requires .NET 4.5
  • Windows XP is not supported anymore because .NET 4.5 requires at least Windows Vista SP2 or Windows Server 2008 SP2/R2 SP1
  • If you have written plugins for HeuristicLab or applications that use HL assemblies you have to update your projects to .NET 4.5

If you have any questions please feel free to ask!

Grammatical Evolution in HeuristicLab

The latest version of HeuristicLab now also includes a plugin for grammatical evolution (GE)! The plugin has been implemented by Sabine Winkler for her Bachelor's thesis, and she kindly contributed her implementation to HeuristicLab, so that we could integrate it into the stable development branch.

So far, the implementation supports two problems: symbolic regression and the artifical ant problem for the Santa Fe trail. However, additional problem types for grammatical evolution can be added easily in a similar way as for tree-based GP (see our documentation on implementing GP problems)

The implementation of GE reuses existing classes and methods for tree-based GP and acts mainly as a translator between the integer vector encoding and the tree encoding. In the mapping process the grammar is used to build a tree from the integer vector. The concept of the mapping process is shown in the following diagram:

The GE plugin also provides different multiple variants of mappers that have been described in literature including depth-first, breath-first, and the π-GE mappers. In GE the genotype to phenotype mappers use a grammar to create a tree from an integer vector. The elements of the integer vector are read from left to right and the tree is built starting from the root symbol of the grammar. For each non-terminal symbol the mapper reads one element from the vector and chooses the alternative for extending the tree based on this value. An example for the depth-first mapper is shown in the following figure.

In GE the genotype to phenotype mapping is prone to the so-called ripple-effect which describes the phenomenon that a small change of the integer-vector might lead to a completely different tree after mapping. This hampers the search process and could lead to premature convergence of the algorithm.

We are happy about contributions to the grammatical evolution implementation or to HeuristicLab in general. So, if you have implemented an algorithm or problem or even only a custom operator feel free to contribute!

Figures (C) Sabine Winkler, with kind permission.

Industrial Challenge at GECCO 2014

At this year’s industrial challenge at the Genetic and Evolutionary Computation Conference GECCO 2014 (http://www.spotseven.de/gecco-challenge/gecco-challenge-2014/) the task was to forecast the emergence of ammonia in a river near Cologne on the basis of rainfall and several (chemical) water properties. On the one hand, this is a highly important issue as cattle dunging and wastewater build the basis for an increasing emergence of ammonia, which is highly toxic and a threat, particularly to fish and other aquatic creatures. On the other hand, this situation poses a challenging test case for modern time series prediction methods.

We decided to participate in this challenge and pursued the following approach, which is a mixture of the preprocessing and modeling strategies pursued in our most recent publications on medical data analysis and stock market data forecasting:

  • First we preprocessed all given data and calculated short term as well as long term moving window averages for all variables.
  • Then we used several regression methods available in HeuristicLab for training models for the formation of ammonia on the basis of the original variables as well as the moving window averages. We used the following modeling techniques: Linear regression, random forests, support vector machines, and genetic programming. All modeling methods were used 10 times with varying modeling parameters for both modeling scenarios. For each scenario we used 80% of the given training data for training and the remaining 20% as validation data.
  • Finally, of all so trained models we selected those 5 models with the best fit on validation data. The eventual test values prediction were calculated as the sample-wise average of the selected models’ outputs.

An then at GECCO results of the competition were announced – we came in second!