COIN belongs to a subgroup of Evolutionary Algorithms that makes use of models to generate solutions. The emphasis is on using some form of model as a repository of “trait” or knowledge extracted from previous candidate solutions. Instead of using genetic operations to create the next generation candidate solutions from the current solutions, the algorithm sampling the new candidates directly from this model, hence eliminate many difficulties involved in designing and performing those genetic operations.

The model in COIN is a joint probability matrix, H. This matrix represents a kind of Markov Chain. An entry in H

1346785290

A coincidence is an adjacent pair of cities in the tour. There are ten coincidences in this tour. They are 1-3, 3-4, 4-6, 6-7, 7-8, 8-5, 5-2, 2-9, 9-0 and 0-1. The joint probability matrix, H, is a square matrix of size n × n. The sum over each row H

Steps of the algorithm

1 Initialise H to a uniform
distribution.

2 Sample a population from H.

3 Evaluate the population.

4 Select two groups of candidates: better, and worse.

5 Use these two groups to update H.

6 Repeate the steps 2-3-4-5 until satisfactory solutions are found.

2 Sample a population from H.

3 Evaluate the population.

4 Select two groups of candidates: better, and worse.

5 Use these two groups to update H.

6 Repeate the steps 2-3-4-5 until satisfactory solutions are found.

These steps are quite standard and are similar to any Estimation Distribution Algorithm except for the step 4 and 5. The precise reason for this step will be discussed later. At this moment, let's discuss these steps. The joint probability matrix, H, is central to this algorithm. It is maintained and updated properly throughout the search cycle.

H

Where k denotes the step size, n the length of a candidate, r

1. Generating the population requires
time O(mn^{2}) and space O(mn)

2. Sorting the population requires time O(m log m)

3. The generator require space O(n^{2})

4. Updating the joint probability matrix requires time O(mn^{2})

2. Sorting the population requires time O(m log m)

3. The generator require space O(n

4. Updating the joint probability matrix requires time O(mn

- Prabhas Chongstitvatana, Warin Wattanapornprom, Panuwat Olanviwitchai, Ronnachai Sirovetnukul, Noppon Kampirom and Parames Chutima, invited paper, "Coincidence Algorithm for Combinatorial Optimisation and Its Applications," Proc. of Electrical Engineering Conference (33th), Chiangmai, Thailand, 1-3 Dec. 2010. ( pdf )
- Wattanapornprom, W. and Chongstitvatana, P.: Multi-objective Combinatorial Optimisation with Coincidence Algorithm, IEEE Congress on Evolutionary Computation, May 18-21, (2009) ( pdf )
- Parames Chutima, Noppon Kampirom, Warin Wattanapornprom and Prabhas Chongstitvattana: Application of Combinatorial optimization with coincidence for Multi-Objective Sequencing Problems on Mixed-Model U-Shaped Assembly Lines in JIT Production Systems, (Best paper award) Annual Conference of Kasetsart University, Bangkok, (2008) (preprint)
- Ronnachai Sirovetnukul and Parames Chutima: The impact of walking time on U-shaped assembly line worker allocation problems, Engineering Journal, Vol 14, issue 2, Apr. (2010) ( pdf )
- Srimongkolkul, O., and Chongstitvatana, P., "Minimizing Makespan Using Node Based Coincidence Algorithm in the Permutation Flowshop Scheduling Problem," in M. Gen et al. (eds.), Industrial Engineering, Management Science and Applications 2015, Lecture Notes in Electrical Engineering 349, DOI: 10.1007/978-3-662-47200-2_33, pp.303-311. (local copy)

last update 17 Aug 2017