方程式诞生而突变体被埋葬的地方

我昨天读过基因编程，所以我想自己尝试实现一些东西。我希望主要关注的是我是否正确实施了其背后的想法。

其背后的思想很简单：给定一个数字和几个参数，生成一个方程式，得出该数字作为解。我已经实现了*，/，+，-和^运算符。

这个世界充满了形式为x + (y - z)的方程式，其中值是随机生成的（以后我可能会随机生成这些运算符）。实现：

将终止其结果不在目标解决方案的预定范围内的方程。
新一代由变异方程和子代组成。父母已不再是新一代。
只剩下一代人时，它会偶尔发生变异，直到他超出可接受的范围。

这会引起一个问题：这是好的方法还是应该改用其他方法？

Program

class Program
{
    static void Main(string[] args)
    {
        new Program();
        Console.Read();
    }

    private static void PrintTree(GeneticTree tree)
    {
        var output = string.Format("{0}: {1:0}{2, 15}[{3}]", tree.Name, tree.GetResult(), string.Empty, tree.GetDisplay());
        Console.WriteLine(output);
    }

    private static void PrintWorld(World world)
    {
        Console.WriteLine("================================");
        Console.WriteLine("Generation {0}", world.Generation);
        foreach (var algorithm in world.Population)
        {
            PrintTree(algorithm);
        }
    }

    public Program()
    {
        var world = new World(targetValue: 50, populationSize: 30, fitnessDelta: 100, mutationChance: 0.2d, minValue: -50, maxValue: 50);

        do
        {
           PrintWorld(world);
        } while (!world.AdvanceGeneration() && !world.Apocalypse);

        if (world.Apocalypse)
        {
            Console.WriteLine("No suitable solution has been found with the given parameters");
        }
        else
        {
            PrintWorld(world);
            Console.WriteLine("Possible solutions after {0} generation(s):", world.Generation);
            foreach (var solution in world.WorkingAlgorithms)
            {
                Console.WriteLine("{0}: {1}", solution.Name, solution.GetDisplay());
            }
        }
    }
}

World

public class World
{
    private static readonly Random Random = new Random();
    private readonly int _populationSize;
    private readonly int _targetValue; 
    private readonly int _fitnessDelta;
    private readonly double _mutationChance;
    private readonly int _minValue;
    private readonly int _maxValue;

    public List<GeneticTree> Population { get; private set; }

    public List<GeneticTree> WorkingAlgorithms { get; private set; }

    public bool Apocalypse { get; private set; }

    public int Generation { get; private set; }

    public World(int targetValue, int populationSize, int fitnessDelta, double mutationChance, int minValue, int maxValue)
    {
        Population = new List<GeneticTree>();
        WorkingAlgorithms = new List<GeneticTree>();
        _targetValue = targetValue;
        _populationSize = populationSize;
        _fitnessDelta = fitnessDelta;
        _mutationChance = mutationChance;
        _minValue = minValue;
        _maxValue = maxValue;
        Initialize();
        Generation = 1;
    }

    private void Initialize()
    {
        for (var i = 0; i < _populationSize; i++)
        {
            var tree = new GeneticTree( _minValue, _maxValue)
            {
                Name = "Algorithm " + i
            };

            Element ops = new AdditionOperator
            {
                LeftElement = new ValueElement(Random.Next(_minValue, _maxValue)),
                RightElement = new SubtractionOperator
                {
                    LeftElement = new ValueElement(Random.Next(_minValue, _maxValue)),
                    RightElement = new ValueElement(Random.Next(_minValue, _maxValue))
                }
            }; // x + (y - z)
            tree.AddOperations(ops);
            Population.Add(tree);
        }
    }

    /// <summary>
    /// Returns true when a solution has been found
    /// </summary>
    public bool AdvanceGeneration()
    {
        var newGeneration = new List<GeneticTree>(Population.Count);

        // Add random roll to determine whether it should mutate or combine with another algorithm
        for (int index = 0; index < Population.Count; index++)
        {
            var algorithm = Population[index];
            if (Random.NextDouble() < _mutationChance)
            {
                algorithm.Mutate();
                newGeneration.Add(algorithm);
            }
            else
            {
                var randomParent = Population.ElementAt(Random.Next(0, Population.Count));
                var child = algorithm.Combine(randomParent);
                newGeneration.Add(child);
            }
        }

        Population = newGeneration;
        ++Generation;
        return CheckFitness();
    }

    private bool CheckFitness()
    {
        var foundSolution = false;

        for (int index = 0; index < Population.Count; index++)
        {
            var algorithm = Population[index];
            var result = algorithm.GetResult();
            if ((Math.Abs(result - _targetValue) < 0.1))
            {
                WorkingAlgorithms.Add(algorithm);
                foundSolution = true;
            }
            else
            {
                if (Math.Max(result, _targetValue) - Math.Min(result, _targetValue) > _fitnessDelta)
                {
                    Population.RemoveAt(index);
                }
            }
        }

        if (Population.Count == 0)
        {
            Apocalypse = true;
        }

        return foundSolution;
    }
}

Element

public abstract class Element
{
    public abstract double GetValue();

    public abstract string GetDisplay();

    public abstract List<Element> Children { get; }
}

Operators

public abstract class Operator : Element
{

}

public abstract class BinaryOperator : Operator
{
    public Element LeftElement { get; set; }

    public Element RightElement { get; set; }

    protected abstract string GetBinarySpecificDisplay();

    protected abstract double GetBinarySpecificValue(double leftValue, double rightValue);

    public override double GetValue()
    {
        var left = LeftElement as ValueElement;
        var leftValue = left != null ? left.Value : LeftElement.GetValue();

        var right = RightElement as ValueElement;
        var rightValue = right != null ? right.Value : RightElement.GetValue();

        return GetBinarySpecificValue(leftValue, rightValue);
    }

    public override List<Element> Children
    {
        get { return new List<Element> { LeftElement, RightElement }; }
    }

    public override string GetDisplay()
    {
        return LeftElement.GetDisplay() + " " + GetBinarySpecificDisplay() + " " + RightElement.GetDisplay();
    }
}

public class AdditionOperator : BinaryOperator
{

    protected override string GetBinarySpecificDisplay()
    {
        return "+";
    }

    protected override double GetBinarySpecificValue(double leftValue, double rightValue)
    {
        return leftValue + rightValue;
    }
}

public class SubtractionOperator : BinaryOperator
{
    protected override double GetBinarySpecificValue(double leftValue, double rightValue)
    {
        return leftValue - rightValue;
    }

    protected override string GetBinarySpecificDisplay()
    {
        return "-";
    }
}

public class DivisionOperator : BinaryOperator
{
    protected override double GetBinarySpecificValue(double leftValue, double rightValue)
    {
        return leftValue / rightValue;
    }

    protected override string GetBinarySpecificDisplay()
    {
        return "/";
    }
}

public class MultiplicationOperator : BinaryOperator
{
    protected override string GetBinarySpecificDisplay()
    {
        return "*";
    }

    protected override double GetBinarySpecificValue(double leftValue, double rightValue)
    {
        return leftValue * rightValue;
    }
}

public class ExclusiveOrOperator : BinaryOperator
{
    protected override string GetBinarySpecificDisplay()
    {
        return "^";
    }

    protected override double GetBinarySpecificValue(double leftValue, double rightValue)
    {
        return (int) leftValue ^ (int) rightValue;
    }
}

ValueElement

public class ValueElement : Element
{
    public double Value { get; set; }

    public ValueElement(double value)
    {
        Value = value;
    }

    public override double GetValue()
    {
        return Value;
    }

    public override string GetDisplay()
    {
        return Value.ToString(CultureInfo.InvariantCulture);
    }

    public override List<Element> Children { get { return null; } }
}

GeneticTree

public class GeneticTree
{
    private const double MutationChance = 0.2d;
    private readonly int _upperBoundary;
    private readonly int _lowerBoundary;
    private readonly static Random Random = new Random();
    private readonly static Type[] BinaryOperations =
    {
        typeof(AdditionOperator), 
        typeof(SubtractionOperator), 
        typeof(DivisionOperator),
        typeof(MultiplicationOperator),
        typeof(ExclusiveOrOperator)
    };
    private bool _canStillSwap;
    private Element _nodes;

    public string Name { get; set; }

    public int Depth { get; private set; }

    public GeneticTree(int minValue, int maxValue)
    {
        _lowerBoundary = minValue;
        _upperBoundary = maxValue;
    }

    public void AddOperations(Element element)
    {
        _nodes = element;
        GetTreeDepth();
    }

    private void GetTreeDepth()
    {
        if (_nodes == null)
        {
            return;;
        }

        Depth = 1;

        if (_nodes.Children != null)
        {
            GetTreeDepth(_nodes.Children);
        }
    }

    private void GetTreeDepth(List<Element> children)
    {
        foreach(var child in children)
        {
            Depth++;
            if (child.Children != null)
            {
                GetTreeDepth(child.Children);
            }
        }
    }

    public double GetResult()
    {
        return _nodes.GetValue();
    }

    public string GetDisplay()
    {
        return _nodes.GetDisplay();
    }

    public void Mutate()
    {
        _canStillSwap = true;
        _nodes = InternalMutate(_nodes);
    }

    private Element InternalMutate(Element element)
    {
        if (!_canStillSwap)
        {
            return element;
        }

        if (MustMutate())
        {
            var valueElement = element as ValueElement;
            if (valueElement != null)
            {
                return MutateValueElement();
            }

            var binaryElement = element as BinaryOperator;
            if (binaryElement != null)
            {
                return MutateBinaryElement(binaryElement);
            }
        }
        else
        {
            if (element.Children != null)
            {
                var binaryOperator = element as BinaryOperator;
                if (binaryOperator != null)
                {
                    var leftChild = binaryOperator.LeftElement;
                    var rightChild = binaryOperator.RightElement;

                    leftChild = InternalMutate(leftChild);
                    rightChild = InternalMutate(rightChild);

                    binaryOperator.LeftElement = leftChild;
                    binaryOperator.RightElement = rightChild;
                }
            }
        }
        return element;
    }

    private Element MutateValueElement()
    {
        _canStillSwap = false;
        return new ValueElement(Random.Next(_lowerBoundary, _upperBoundary));
    }

    private Element MutateBinaryElement(BinaryOperator element)
    {
        var currentType = element.GetType();
        var newType = BinaryOperations.Except(new[] { currentType }).OrderBy(x => Guid.NewGuid()).First();
        var newElement = (BinaryOperator) Activator.CreateInstance(newType);
        newElement.LeftElement = element.LeftElement;
        newElement.RightElement = element.RightElement;
        _canStillSwap = false;
        return newElement;
    }

    private bool MustMutate()
    {
        return Random.NextDouble() < MutationChance;
    }

    public GeneticTree Combine(GeneticTree otherParent)
    {
        // We will assume both trees have the same layout and depth.
        // For example:
        //     +                          *
        //  5     -                   3       ^
        //      6   2                       4    2

        if (Depth != otherParent.Depth)
        {
            throw new ApplicationException("Trees are not similarly constructed");
        }

        var pivot = Depth / 2;
        if (pivot <= 1)
        {
            return this;
        }

        if (_nodes.Children != null)
        {
            var binaryNodeMom = _nodes as BinaryOperator;
            var binaryNodeDad = otherParent._nodes as BinaryOperator;
            if (binaryNodeMom != null && binaryNodeDad != null)
            {
                var momLeftElement = binaryNodeMom.LeftElement;
                var dadRightElement = binaryNodeDad.RightElement;

                var tree = new GeneticTree(_lowerBoundary, _upperBoundary)
                {
                    Name = "Nameless child"
                };

                var child = binaryNodeMom;
                child.LeftElement = momLeftElement;
                child.RightElement = dadRightElement;

                tree.AddOperations(child);
                return tree;
            }
        }

        return this;
    }
}

样本输出：

GitHub

那些想要玩转它或喜欢更舒适的查看方式的人，可以从我的GitHub获取代码。

我特此提名“有史以来最好的头衔”这个问题。

@RubberDuck：虽然我同意，但标题通常应该至少要多一点……有问题。阅读标题只会使您想要单击它，但不会引起对问题区域的理解。但是我喜欢...

我添加了一个答案，但是还有更多问题。我将它们留给其他审阅者指出。如果您有兴趣，可以在更合适的时间查看。

#1 楼

您正在将算法分为两类：有效算法和非有效算法；这是相当Manichean。您应该尝试设计一种算法不能“起作用”但可以“比其他方法更好地接近预期结果”的东西。换句话说，不要试图找到“谁有效”，而是“谁更好”。 IMO最好的方法是获得一代人的所有结果，将它们进行比较以查看哪些结果更接近预期结果，哪些结果更接近预期结果。换句话说，您应该将算法称为“相对适应度”，以了解哪种解决方案比其他解决方案“相对更好”。

这种相对适应度将帮助您生成一个新一代，具有以下步骤：

为每个算法分配一个生存率，相对于它的相对适应度（越接近预期结果，生存率越高）。
对于您种群中的每种算法，请获取一个介于0和1之间的随机数。
删除其随机数大于其生存百分比的算法。
保留下一代的生存算法。
通过创建算法并将剩余的算法组合起来，从而使新一代产品变得完整。

如果这样做，那么您几乎应该能够始终保持各代产品之间的最佳算法，但您还将保留其他一些突变和/或组合可能无法使用的可能会产生比您当前最好的更好的方法。此过程“您可能会拥有出乎意料的才能”对于避免本地极端情况很有用。

#2 楼

代码闻起来

不要在构造函数中做所有工作

这段代码看起来像是有用的：

static void Main(string[] args)
{
    new Program();
    Console.Read();
}

构造函数中的所有代码都可以放在Main中。我们将代码从Main移至实例类的原因是，我们可以使用多种配置来运行它们。例如，这里没有办法与另一个Program一起运行World。可以更改它，以便代替，您可以轻松地找出要在Program.cs中进行的伴随更改：

/>以下可能是接口：

static void Main(string[] args)
{
    var world = new World(
        targetValue: 50, 
        populationSize: 30, 
        fitnessDelta: 100, 
        mutationChance: 0.2d, 
        minValue: -50, 
        maxValue: 50);
    new Program(world).Run(); // I can reuse `Run` method elsewhere now
    Console.Read();
}

不要对代码的可用性施加不必要的限制。
顺便说一下，这是在C ++中定义接口的方式;如果这是C ++使用的习惯，则应在编码C＃时摆脱它。

如果返回类型是集合或可枚举，请不要返回null。

这是个坏消息：

public abstract class Element
{
    public abstract double GetValue();

    public abstract string GetDisplay();

    public abstract List<Element> Children { get; }
}

public abstract class Operator : Element
{

}

实际使用的唯一位置是：

    List<Element> Children { get { return null; } }

如果您返回一个空列表，则以上两个null检查都不是必需的。

不要对未使用的变量进行null检查

我说“ [Element.Children]实际上被使用了”，因为在其他情况下会对其进行空检查然后不使用它！此处：

    private void GetTreeDepth()
    {
        // ... SNIP

        if (_nodes.Children != null)
        {
            GetTreeDepth(_nodes.Children);
        }
    }

    private void GetTreeDepth(List<Element> children)
    {
        foreach(var child in children)
        {
            Depth++;
            if (child.Children != null)
            {
                GetTreeDepth(child.Children);
            }
        }
    }

此处：

if (element.Children != null)
{
    var binaryOperator = element as BinaryOperator;

这似乎是一个遗留的伪运行时-类型检查。这些一次的空检查可能会用于检查变量是否为二进制运算符，但是当添加普通的类型检查时，它们变得毫无用处。

GeneticTree中的关注点分离
/>

GeneticTree有两件事：它为种群生成变异的个体，也就是那些个体。 br />

if (_nodes.Children != null)
{
    var binaryNodeMom = _nodes as BinaryOperator;

vs.
私人布尔值_canStillSwap;

private const double MutationChance = 0.2d;
private readonly int _upperBoundary;
private readonly int _lowerBoundary;
private readonly static Random Random = new Random();
private readonly static Type[] BinaryOperations= ...;

就像当您看到在方法中组合在一起的几行代码时一样，您应该在看到大量字段时提取一个方法
另一个提示是MutationChance是const，Random和BinaryOperations是static，_upperBoundary和_lowerBoundary不是静态的，但是它们在算法运行时不会改变，它们需要传递围绕它们进行修改，只是因为无法轻易将它们设置为静态。如果您可以从域中找到更好的名称，例如GeneticTreeFactory，则应该将第一组字段提取到MutationGenerator。

编程黑洞网

方程式诞生而突变体被埋葬的地方

评论

#1 楼

#2 楼