欢迎来到多目标优化领域。这是我写论文的领域。求解这类问题的算法有很多,但最著名的两个可能是NSGA-II和SPEA2。

我可以指给你看吗 http://jmetalnet.sourceforge.net/ ?

其思想是,您将生成包含输入的随机向量的总体,这些输入在您的100^6个可能解的域中。这些种群将发生变异并相互交配,以产生新的解决方案,从这些新种群中,它们被向下选择,从而选择更偏好的解决方案保留下来(并在进化中幸存下来)。

在多世界中,比较不同解决方案的适用性可能会遇到挑战。但在你的单目标世界中,比较适合度很容易:你只需要决定你想要更高还是更低的数字。看起来你想要更高的。

概述

1. 创建解的随机总体。
2. 在你的解决方案中随机变异/交叉。
4. 将样本降回最佳解的初始种群大小。
6. 输出最终生成。

结果:

结果格式为之前、之后的平均分数,最大值为600

295.23,542.12

298.53,565

301.814,579.334

PopSize=10000,NumGens=500,MutRate=0.2,CrossRate=0.8

我在大约20分钟内编写了这段代码,所以它并不意味着优雅或令人敬畏。我希望它能让人明白这一点。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace moo_in_csharp
{
    internal class Individual
    {
        public int[] Decisions;
        public double Fitness;
        private int _numdecisions = 6;

        /// <summary>
        /// Default constructor.
        /// </summary>
        public Individual()
        {
            Decisions = new int[_numdecisions];
        }

        /// <summary>
        /// Replaces first half of decisions with those of the mate.
        /// </summary>
        /// <param name="mate"></param>
        public void Crossover(Individual mate)
        {
            int crossoverPoint = _numdecisions / 2;
            for (int i = 0; i < crossoverPoint; i++)
            {
                Decisions[i] = mate.Decisions[i];
            }
        }

        /// <summary>
        /// Simple fitness function that computes sum of a+b+c+d+e+f.
        /// </summary>
        public double Evaluate()
        {
            Fitness = Decisions.Sum();
            return Fitness;
        }

        /// <summary>
        /// Assigns random values to its decisions.
        /// </summary>
        public void Generate()
        {
            for (int i = 0; i < _numdecisions; i++)
            {
                Decisions[i] = Program.rand.Next(0, 101);
            }
        }

        /// <summary>
        /// Randomly mutate select decisions.
        /// </summary>
        public void Mutate()
        {
            for (int i = 0; i < _numdecisions; i++)
            {
                Decisions[i] = Program.rand.Next(0, 101);
            }
        }
    }

    internal class Program
    {
        public static Random rand = new Random();

        private static void Main(string[] args)
        {
            //parameters
            int populationSize = 100;
            int numGenerations = 50;
            double mutationRate = 0.2;
            double crossoverRate = 0.8;

            //build initial population
            List<Individual> solutions = new List<Individual>();
            for (int i = 0; i < populationSize; i++)
            {
                var solution = new Individual();
                solution.Generate();
                solution.Evaluate();
                solutions.Add(solution);
            }

            //calculate average score of initial population
            var averageScoreBefore = solutions.Select(x => x.Evaluate()).Average();

            //iterate across number of generations
            for (int i = 0; i < numGenerations; i++)
            {
                //build offspring by mating sequential pairs of solutions
                var offspring = new List<Individual>();
                for (int e = 0; e < solutions.Count() - 1; e += 2)
                {
                    if (rand.NextDouble() < crossoverRate)
                    {
                        var newIndividual = new Individual();
                        solutions[e].Decisions.CopyTo(newIndividual.Decisions, 0);
                        newIndividual.Crossover(solutions[e + 1]);
                        offspring.Add(newIndividual);
                    }
                }

                //add our offspring to our solutions
                solutions.AddRange(offspring);

                //mutate solutions at a low rate
                foreach (var solution in solutions)
                {
                    if (rand.NextDouble() < mutationRate)
                    {
                        solution.Mutate();
                    }
                }

                //sort our solutions and down-sample to initial population size
                solutions = solutions.OrderByDescending(x => x.Evaluate()).ToList();
                solutions = solutions.Take(populationSize).ToList();
            }

            //calculate average score after
            var averageScoreAfter = solutions.Select(x => x.Evaluate()).Average();
            Debug.WriteLine(averageScoreBefore + "," + averageScoreAfter);
        }
    }
}

其他注释

您的运行时间主要取决于您的健身评分函数。对于简单的数学函数,此运行时并不困难。显然,如果涉及到一个过程,那么您应该将评估的数量保持在最低限度。这就是我在攻读博士学位时研究的内容,并开发了一种新算法,名为GALE:

• http://ieeexplore.ieee.org/document/7105950/

您可以尝试使用元启发式/随机局部搜索算法来解决这类问题,如许多评论和BurnsCA的解决方案中所述。

模拟退火和遗传算法都是例子,但还有更多例子。 这种方法是否可行,取决于计算目标函数变化的速度,即评估解决方案的质量及其变化。

如果模拟的输出具有微小变化会显著改变结果的特性,那么它可能是也可能不是比暴力强制通过一些随机分配并选择最佳分配更好的方法。你必须进行实验。

http://www.centerspace.net/doc/NMath/user/simulated-annealing-85273.htm

您的“目标函数”,即您试图最大化(或最小化)的值是模拟的输出。

虽然算法本身的实现并不困难,但它们的各个方面的高效实现都很重要。

你需要做的是定义一个邻域函数,即从解(或状态,如果你喜欢)到另一个解的一种方式。 一 参数如果1-opt没有足够快地显示改进,您也可以尝试2-opt移动或更多。

如果可能的话

最简单的方法(通常称为下降法)是随机移动到相邻的解决方案,如果它发现了更好的(在您的情况下更高的目标函数)值,则将其作为新的解决方案,然后重复该步骤,直到找不到更多的改进。

这种方法的问题是,你很快就会陷入局部极大值。模拟退火提供了一种试图避免这种情况的方法,它不仅选择改进,而且选择非改进动作的概率取决于当前的“温度”,这只是一个变量,您可以根据一些规则减少每次迭代 退火计划

由于实现这些方法的关键不在于整体算法本身(尽管它确实需要一点时间),而在于实现您的邻域和邻域评估函数,我个人认为使用一些框架不会节省很多时间。

如果这是一次性的,而上述方法不可行,您也可以考虑跨数千台机器并行计算,以获得最优解。E、 g.Azure Batch或类似服务。由于您可以在30分钟内测试50 mio组合(在一台机器上,无需并行化?),原则上,您可以提供20000台虚拟机,并在30分钟内测试所有组合。

// Example linear calculation
public int Calculation(int a, int b, int c, int d, int e, int f)
{
    int result = 0;
    unchecked
    {
        result = (int)((double)a * Math.Tan((double)b * Math.PI / ((double)c + 0.001)));
        result += d + e + f;
    }

    return result;
}


var rand = new Random();

// The currently best known solution set
var best = new int[6] { 1, 1, 1, 1, 1, 1 };

// Score for best known solution set
int bestScore = int.MinValue;

// loop variables
int score;
var work = new int[6];

// Loop as appropriate.
for (int i=0; i<500; i++)
{
    // Copy over the best solution to modify it
    best.CopyTo(work, 0);

    // Change one of the parameters of the best solution
    work[rand.Next() % 6] = rand.Next() % 101;

    // Calculate new score with modified solution
    score = Calculation(work[0], work[1], work[2], work[3], work[4], work[5]);

    // Only keep this solution if it's better than anything else
    if (score > bestScore)
    {
        work.CopyTo(best, 0);
        bestScore = score;
    }
}

上述方法很快收敛到一个解,主要是因为计算函数非常友好。500次迭代后:

int[6] { 98, 1, 2, 98, 99, 100 }

最优解决方案是 { 100, 1, 2, 100, 100, 100 }

注意,这种局部优化方法只适用于大多数线性问题。

有一个 nifty image 在维基百科页面上 hill climbing 这种算法显示了这种方法的本质。