Permalink
Find file Copy path
3826dfa Feb 15, 2018
2 contributors

Users who have contributed to this file

@giacomelli @AntonyCorbett
118 lines (107 sloc) 5.65 KB
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using GeneticSharp.Domain.Chromosomes;
using GeneticSharp.Domain.Randomizations;
namespace GeneticSharp.Domain.Crossovers
{
/// <summary>
/// Ordered Crossover (OX1).
/// <remarks>
/// Also know as: Order Crossover.
/// <para>
/// A portion of one parent is mapped to a portion of the other parent.
/// From the replaced portion on, the rest is filled up by the remaining genes, where already present genes are omitted and the order is preserved.
/// <see href="http://en.wikipedia.org/wiki/Crossover_(genetic_algorithm)#Crossover_for_Ordered_Chromosomes">Crossover for Ordered Chromosomes</see>
/// </para>
/// <para>
/// The Ordered Crossover method is presented by Goldberg, is used when the problem is of order based,
/// for example in Ushaped assembly line balancing etc. Given two parent
/// chromosomes, two random crossover points are selected
/// partitioning them into a left, middle and right portion. The
/// ordered two-point crossover behaves in the following way:
/// child1 inherits its left and right section from parent1, and its middle section is determined.
/// <see href="http://arxiv.org/ftp/arxiv/papers/1203/1203.3097.pdf">A Comparative Study of Adaptive Crossover Operators for Genetic Algorithms to Resolve the Traveling Salesman Problem</see>
/// </para>
/// <para>
/// The order crossover operator (Figure 4) was proposed by Davis (1985).
/// The OX1 exploits a property of the path representation, that the order of cities (not their positions) are important.
/// <see href="http://lev4projdissertation.googlecode.com/svn-history/r100/trunk/reading/read/aiRev99.pdf">Genetic Algorithms for the Travelling Salesman Problem - A Review of Representations and Operators</see>
/// </para>
/// <para>
/// Order 1 Crossover is a fairly simple permutation crossover.
/// Basically, a swath of consecutive alleles from parent 1 drops down,
/// and remaining values are placed in the child in the order which they appear in parent 2.
/// <see href="http://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/Order1CrossoverOperator.aspx">Order 1 Crossover</see>
/// </para>
/// </remarks>
/// </summary>
[DisplayName("Ordered (OX1)")]
public sealed class OrderedCrossover : CrossoverBase
{
#region Constructors
/// <summary>
/// Initializes a new instance of the <see cref="GeneticSharp.Domain.Crossovers.OrderedCrossover"/> class.
/// </summary>
public OrderedCrossover()
: base(2, 2)
{
IsOrdered = true;
}
#endregion
#region Methods
/// <summary>
/// Performs the cross with specified parents generating the children.
/// </summary>
/// <param name="parents">The parents chromosomes.</param>
/// <returns>The offspring (children) of the parents.</returns>
protected override IList<IChromosome> PerformCross(IList<IChromosome> parents)
{
var firstParent = parents[0];
var secondParent = parents[1];
if (parents.AnyHasRepeatedGene())
{
throw new CrossoverException(this, "The Ordered Crossover (OX1) can be only used with ordered chromosomes. The specified chromosome has repeated genes.");
}
var middleSectionIndexes = RandomizationProvider.Current.GetUniqueInts(2, 0, firstParent.Length);
Array.Sort(middleSectionIndexes);
var middleSectionBeginIndex = middleSectionIndexes[0];
var middleSectionEndIndex = middleSectionIndexes[1];
var firstChild = CreateChild(firstParent, secondParent, middleSectionBeginIndex, middleSectionEndIndex);
var secondChild = CreateChild(secondParent, firstParent, middleSectionBeginIndex, middleSectionEndIndex);
return new List<IChromosome>() { firstChild, secondChild };
}
/// <summary>
/// Creates the child.
/// </summary>
/// <returns>The child.</returns>
/// <param name="firstParent">First parent.</param>
/// <param name="secondParent">Second parent.</param>
/// <param name="middleSectionBeginIndex">Middle section begin index.</param>
/// <param name="middleSectionEndIndex">Middle section end index.</param>
private static IChromosome CreateChild(IChromosome firstParent, IChromosome secondParent, int middleSectionBeginIndex, int middleSectionEndIndex)
{
var middleSectionGenes = firstParent.GetGenes().Skip(middleSectionBeginIndex).Take((middleSectionEndIndex - middleSectionBeginIndex) + 1);
using (var secondParentRemainingGenes = secondParent.GetGenes().Except(middleSectionGenes).GetEnumerator())
{
var child = firstParent.CreateNew();
for (int i = 0; i < firstParent.Length; i++)
{
var firstParentGene = firstParent.GetGene(i);
if (i >= middleSectionBeginIndex && i <= middleSectionEndIndex)
{
child.ReplaceGene(i, firstParentGene);
}
else
{
secondParentRemainingGenes.MoveNext();
child.ReplaceGene(i, secondParentRemainingGenes.Current);
}
}
return child;
}
}
#endregion
}
}