Constructive cooperative coevolution

The constructive cooperative coevolutionary algorithm (also called C3) is a global optimisation algorithm in artificial intelligence based on the multi-start architecture of the greedy randomized adaptive search procedure (GRASP).[1][2] It incorporates the existing cooperative coevolutionary algorithm (CC).[3] The considered problem is decomposed into subproblems. These subproblems are optimised separately while exchanging information in order to solve the complete problem. An optimisation algorithm, usually but not necessarily an evolutionary algorithm, is embedded in C3 for optimising those subproblems. The nature of the embedded optimisation algorithm determines whether C3's behaviour is deterministic or stochastic.

The C3 optimisation algorithm was originally designed for simulation-based optimisation[4][5] but it can be used for global optimisation problems in general.[6] Its strength over other optimisation algorithms, specifically cooperative coevolution, is that it is better able to handle non-separable optimisation problems.[4][7]

An improved version was proposed later, called the Improved Constructive Cooperative Coevolutionary Differential Evolution (C3iDE), which removes several limitations with the previous version. A novel element of C3iDE is the advanced initialisation of the subpopulations. C3iDE initially optimises the subpopulations in a partially co-adaptive fashion. During the initial optimisation of a subpopulation, only a subset of the other subcomponents is considered for the co-adaptation. This subset increases stepwise until all subcomponents are considered. This makes C3iDE very effective on large-scale global optimisation problems (up to 1000 dimensions) compared to cooperative coevolutionary algorithm (CC) and Differential evolution.[8]

The improved algorithm has then been adapted for multi-objective optimization.[9]

Algorithm

As shown in the pseudo code below, an iteration of C3 exists of two phases. In Phase I, the constructive phase, a feasible solution for the entire problem is constructed in a stepwise manner. Considering a different subproblem in each step. After the final step, all subproblems are considered and a solution for the complete problem has been constructed. This constructed solution is then used as the initial solution in Phase II, the local improvement phase. The CC algorithm is employed to further optimise the constructed solution. A cycle of Phase II includes optimising the subproblems separately while keeping the parameters of the other subproblems fixed to a central blackboard solution. When this is done for each subproblem, the found solution are combined during a "collaboration" step, and the best one among the produced combinations becomes the blackboard solution for the next cycle. In the next cycle, the same is repeated. Phase II, and thereby the current iteration, are terminated when the search of the CC algorithm stagnates and no significantly better solutions are being found. Then, the next iteration is started. At the start of the next iteration, a new feasible solution is constructed, utilising solutions that were found during the Phase I of the previous iteration(s). This constructed solution is then used as the initial solution in Phase II in the same way as in the first iteration. This is repeated until one of the termination criteria for the optimisation is reached, e.g. a maximum number of evaluations.

{Sphase1} ← ∅
while termination criteria not satisfied do
    if {Sphase1} = ∅ then
        {Sphase1} ← SubOpt(∅, 1)
    end if
    while pphase1 not completely constructed do
        pphase1 ← GetBest({Sphase1})
        {Sphase1} ← SubOpt(pphase1, inext subproblem)
    end while
    pphase2 ← GetBest({Sphase1})
    while not stagnate do
        {Sphase2} ← ∅ 
        for each subproblem i do
            {Sphase2} ← SubOpt(pphase2,i)
        end for
        {Sphase2} ← Collab({Sphase2})
        pphase2 ← GetBest({Sphase2})
    end while
end while

Multi-objective optimisation

The multi-objective version of the C3 algorithm [9] is a Pareto-based algorithm which uses the same divide-and-conquer strategy as the single-objective C3 optimisation algorithm . The algorithm again starts with the advanced constructive initial optimisations of the subpopulations, considering an increasing subset of subproblems. The subset increases until the entire set of all subproblems is included. During these initial optimisations, the subpopulation of the latest included subproblem is evolved by a multi-objective evolutionary algorithm. For the fitness calculations of the members of the subpopulation, they are combined with a collaborator solution from each of the previously optimised subpopulations. Once all subproblems' subpopulations have been initially optimised, the multi-objective C3 optimisation algorithm continues to optimise each subproblem in a round-robin fashion, but now collaborator solutions from all other subproblems' subspopulations are combined with the member of the subpopulation that is being evaluated. The collaborator solution is selected randomly from the solutions that make up the Pareto-optimal front of the subpopulation. The fitness assignment to the collaborator solutions is done in an optimistic fashion (i.e. an "old" fitness value is replaced when the new one is better).

Applications

The constructive cooperative coevolution algorithm has been applied to different types of problems, e.g. a set of standard benchmark functions,[4][6] optimisation of sheet metal press lines[4][5] and interacting production stations.[5] The C3 algorithm has been embedded with, amongst others, the differential evolution algorithm[10] and the particle swarm optimiser[11] for the subproblem optimisations.

gollark: https://upload.wikimedia.org/wikipedia/commons/8/8f/Unit_circle.svg
gollark: I think the unit circle thing is probably a better way to think about it than your weird vaguely circle-looking things.
gollark: Are you an antinatalist now?
gollark: I... may have some pictures stored in a backup somewhere?
gollark: It was quite fun and popular, but broke because of poor performance.

See also

References
  1. T.A. Feo and M.G.C. Resende (1989) "A probabilistic heuristic for a computationally difficult set covering problem". Operations Research Letters, 8:67–71, 1989.
  2. T.A. Feo and M.G.C. Resende (1995) "Greedy randomized adaptive search procedures". Journal of Global Optimization, 6:109–133, 1995.
  3. M. A. Potter and K. A. D. Jong, "A cooperative coevolutionary approach to function optimization", in PPSN III: Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature London, UK:Springer-Verlag, 1994, pp. 249–257.
  4. Glorieux E., Danielsson F., Svensson B., Lennartson B., "Optimisation of interacting production stations using a Constructive Cooperative Coevolutionary approach", 2014 IEEE International Conference on Automation Science and Engineering (CASE), pp.322-327, August 2014, Taipei, Taiwan
  5. Glorieux E., Svensson B., Danielsson F., Lennartson B., "A Constructive Cooperative Coevolutionary Algorithm Applied to Press Line Optimisation", Proceedings of the 24th International Conference on Flexible Automation and Intelligent Manufacturing (FAIM), pp.909-917, May 2014, San Antonio, Texas, USA
  6. Glorieux E., Svensson B., Danielsson F., Lennartson B.: "Constructive cooperative coevolution for large-scale global optimisation", Journal of Heuristics, 2017.
  7. Glorieux E., Danielsson F., Svensson B., Lennartson B.: "Constructive cooperative coevolutionary optimisation for interacting production stations", International Journal of Advanced Manufacturing Technology, 2015.
  8. Glorieux E., Svensson B., Danielsson F., Lennartson B., "Improved Constructive Cooperative Coevolutionary Differential Evolution for Large-Scale Optimisation", 2015 IEEE Symposium Series on Computational Intelligence, December 2015
  9. Glorieux E., Svensson B., Danielsson F., Lennartson B., "Multi-objective constructive cooperative coevolutionary optimization of robotic press-line tending", Engineering Optimization, Vol. 49, Iss. 10, 2017, pp 1685-1703
  10. Storn, Rainer, and Kenneth Price. "Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces", Journal of global optimization 11.4 (1997): 341-359.
  11. Eberhart, Russ C., and James Kennedy. "A new optimizer using particle swarm theory", Proceedings of the sixth international symposium on micro machine and human science. Vol. 1. 1995.
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.