Grouping Evolution strategies

Saturday 2, November, 2013

 

Falkenauer  defines a grouping or assignment type problem as the one where the aim is partitioning a set V of n items into a collection of mutually disjoint subsets (groups). This definition says that in a grouping problem the aim is to partition the members of V into D  different groups such that each item being assigned exactly to one group. Originally it is assumed that the ordering of groups is not relevant in grouping problems. However, there are many grouping type problems in which the ordering of groups is important. Many NP-hard combinatorial optimization problems such as graph coloring problem, bin-packing problem, batch-processing machine scheduling problem, line-balancing problem, timetabling problem, identical/non-identical parallel-machines scheduling problem, cell formation problem, pickup and delivery problem etc, are well used examples of grouping problems. In most of grouping problems, not all possible groupings are permitted since the group formations must be in such a way that a number of constraints being satisfied. Besides grouping constraints, the groups are usually formed based on an objective function which is founded on the composition of groups. Therefore, the building blocks that should be taken into consideration in an evolutionary search should be the groups or the group segments, but not the items isolatedly.

In 1994, Falkenauer explained that the commonly used representations suffer from redundancies. Let us consider the most predominant representation in grouping problems in both evolutionary and local search methods, namely the number encoding. In the number encoding, the kth element indicates the ID of the group to which item k belongs. For example the individual 21321 encodes the solution in which the first item is in group 2, second in 1, third in 3, and so on. However, it is easy to see that the individual 12312 encodes exactly the same solution, if the naming or the ordering of groups is irrelevant. Drawbacks of this representation have been presented in the literature. Consequently, Falkenauer proposed the group encoding and used it in genetic algorithm (GA). The idea of group encoding is that those items belonging to the same group are placed into the same partition. For instance, the exampled individual can be represented as {{2,5}, {4,1}, {3}}. Using this encoding scheme, search operators can work on groups rather than items unlike in number encoding (note that the ordering within and between partitions is irrelevant). The rationale is that in grouping problems it is the groups that constitute the underlying building blocks, i.e. the smallest piece of a solution, which can convey information on the expected quality of the solution they are part of. Thus, operators that allow the propagation of such information are more appropriate for evolutionary search methods applied to grouping problems. The name grouping genetic algorithm (GGA) has been used by Falkenauer in 1994 to refer to a genetic algorithm that uses group encoding and related operators for solving grouping problems. Thereafter, researchers have reported many successful application of GGA on solving variety of grouping problems. 

To our knowledge all researches that have used group related encoding and operators, have relied upon GA as their evolutionary search engine. In other words, they all have applied GGA and there is no effort on developing the grouping version of other meta-heuristics (e.g., simulated annealing (SA), tabu search (TS), evolution strategies (ES), etc). Although it may seem easy to develop the grouping version of SA (GSA) or even TS (GTS) (because the only difference between GSA (or GTS) with SA (or TS) is in the generation of the neighbor solution and this may be fixed using GGA operators to generate the neighborhood solutions), this is not the case with ES. The difficulty with developing the grouping version of ES (GES) is due to the following facts.

1) ES (as will be described later) owns a Gaussian mutation to produce new real-valued solution vectors during the search process. To introduce GES, we should develop a new comparable mutation which works based on the role of groups, while keeping the major characteristics of the classic ES mutation. 

2) Originally, ES has been introduced for optimizing non-linear functions in continuous space. But grouping problems are all discrete. GES keeps the new mutation working in continuous space while using the consequences in discrete space. 

To introduce grouping evolution strategies (GES) for grouping problems that are discrete in nature, we must develop operators having major characteristics of the original ones and being respondent to the structure of such problems. GES uses a mutation operator analogous to the original one that works with groups instead of scalars and uses it in a two phase procedure to generate the new solution. The main characteristic of the new mutation mechanism is that it works in continuous space while the consequences are used in discrete space.

The basic steps of the (1+lambda)-GES family can be represented as a pseudocode shown in the following Figure, where f(x) denotes the objective function or fitness value corresponding to solution X

 

 

To find more details on various module used in GES please see the following paper. More ideas can also be found in the publicatins list provided bellow. With reference to a number of issues observed during the developement of GES, we can justify that why we believe GES is much more flexible than GGA and can be regarded as an effective solver for grouping problems (please see the paper provided via the following link).

 
To download an introductory paper on GES
     

To download the Powerpoint slides of GES 

     
To download the Powerpoint slides of an application of GES on bin packing problem (in Persian) 
     
To download the Matlab source code of GES for solving the bin packing problem 
 
 

     Researches on Grouping Evolution Strategies


  1. Soltanpour Z (2015). A Grouping Evolutionary-Based Method for Bin 2D Packing ProblemMs.C Thesis, Azad University, South Tehran branch, Iran (in Persian).

  2. Husseinzadeh Kashan A, Akbari A, Ostadi B (2015). Grouping evolution strategies: a new efficient solution approach for grouping problems. Applied Mathematical Modeling, 39, 2703-2720.

  3. Vardi Chari M (2015). Capacity control with customer upgarading problem under variable capacity utilization allowed using grouping evolution strategiesMs.C Thesis, Tarbiat Modares University, Iran (in Persian)

  4. Vosoughpour F (2014). A grouping evolution strategy algorithm for a location-inventory-routing problem in the distribution network with multiple objectivesMs.C Thesis, Azad University, South Tehran branch, Iran (in Persian).

  5. Husseinzadeh Kashan A, Rezaee B, Karimiyan S (2013). An efficient approach for unsupervised fuzzy clustering based on grouping evolution strategyPattern Recognition, 46, 1240-1254

  6. Husseinzadeh Kashan A, Husseinzadeh Kashan M, Karimiyan S (2013). A particle swarm optimizer for grouping problemsInformation Sciences252, 81-95.

  7. Ghadirnejad M, Husseinzadeh Kashan A, Rismanchian F (2013). A new competitive method for solving assembly line balancing problem. 1st International Conference on New Directions in Business, Management, Finance and Economics.

  8. Hosseinzadeh N (2013). A new algorithm for Pickup and delivery problem with time windows based on grouping evolution strategiesMs.C Thesis, Azad University, Science and Research branch, Iran (in Persian).

  9. Keshmiri M (2013). Efficient solution method(s) for job scheduling on parallel machines in a single and multi objective environment using grouping evolution strategiesMs.C Thesis, Azad University, Science and Research branch, Iran (in Persian).

  10. Ghadirinejad M (2010). Single-sided Assembly Line Balancing Using A Metaheuristic AlgorithmMs.C Thesis, Azad University, South Tehran branch, Iran (in Persian).

  11. Husseinzadeh Kashan A, Jenabi M, Husseinzadeh Kashan M (2009). A new solution approach for grouping problems based on evolution strategies. SoCPaR 2009 IEEE International Conference of Soft Computing and Pattern Recognition, 88-93.

  12. HusseinzadehKashan A (2009). Upper and Lower Bound Procedures for Batch-processing Machine Scheduling Problems With Different Capacity Requirement for Jobs. Unpublished Ph.D. Dissertation, Amirkabir University of Technology, Iran (in Pesian).