组合优化算法

1. 组合优化问题的一般求解方法有哪些

组合（最）优化问题是最优化问题的一类。最优化问题似乎自然地分成两类：一类是连续变量的问题，另一类是离散变量的问题。具有离散变量的问题，我们称它为组合的。在连续变量的问题里，一般地是求一组实数，或者一个函数；在组合问题里，是从一个无限集或者可数无限集里寻找一个对象——典型地是一个整数，一个集合，一个排列，或者一个图。一般地，这两类问题有相当不同的特色，并且求解它们的方法也是很不同的。

2. 优化算法是什么呢

优化算法是指对算法的有关性能进行优化，如时间复杂度、空间复杂度、正确性、健壮性。

大数据时代到来，算法要处理数据的数量级也越来越大以及处理问题的场景千变万化。为了增强算法的处理问题的能力，对算法进行优化是必不可少的。算法优化一般是对算法结构和收敛性进行优化。

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

遗传算法

遗传算法也是受自然科学的启发。这类算法的运行过程是先随机生成一组解，称之为种群。在优化过程中的每一步，算法会计算整个种群的成本函数，从而得到一个有关题解的排序，在对题解排序之后，一个新的种群----称之为下一代就被创建出来了。首先，我们将当前种群中位于最顶端的题解加入其所在的新种群中，称之为精英选拔法。新种群中的余下部分是由修改最优解后形成的全新解组成。

常用的有两种修改题解的方法。其中一种称为变异，其做法是对一个既有解进行微小的、简单的、随机的改变；修改题解的另一种方法称为交叉或配对，这种方法是选取最优解种的两个解，然后将它们按某种方式进行组合。尔后，这一过程会一直重复进行，直到达到指定的迭代次数，或者连续经过数代后题解都没有改善时停止。

3. 请问组合优化和非线性整数规划的区别是什么

先问一下提问者，在什么情形下想要了解这方面的内容？提出这样的问题，可以看出你对这方面的了解几乎是零……
组合优化和非线性整数规划根本不是能在一个范畴上比较的东西啊。组合优化是运筹学的后继课程，同时也是运筹学的一个重要独立分支，是一类重要的优化问题，它又称离散优化，是通过数学方法去寻找离散事件的最优编排、分组、次序或筛选等。而非线性整数规划则是将事件抽象成数学表达式后的一类问题，可以看作组合优化问题的一类分支，或更准确的说，解决组合优化问题的算法的一个分支。
另外，组合优化是各种离散问题的总和，它包含了各式各样的问题，最常见的有装箱问题、平行机问题、背包问题、图论问题（最短路径、一笔画问题、最小生成树问题、着色问题等）、旅行商问题、在线问题等等很多，每种问题都有自己的精确解和近似解的各种算法，其中任意一个问题的研究都可以写成一本书了，而所谓的组合优化的比较新的解决方法……这个东西是不存在的……非线性整数规划也是的，其实一些比较传统的算法不见得不好，建议你去找一本讲数学规划和组合优化的书去系统了解一下。
至于国内外研究现状，也不是一两句话能说的清的，还是一句话，去搜近时间的论文吧。

4. 什么叫组合优化

组合优化（Combinatorial Optimization）问题的目标是从组合问题的可行解集中求出最优解，通常可描述为：令Ω＝{s1，s2，…，sn}为所有状态构成的解空间，C(si)为状态si对应的目标函数值，要求寻找最优解s*，使得对于所有的si∈Ω，有C(s*)＝minC(si)。组合优化往往涉及排序、分类、筛选等问题，它是的一个重要分支。
典型的组合优化问题有旅行商问题（Traveling Salesman Problem－TSP）、加工调度问题（Scheling Problem，如Flow-Shop，Job-Shop）、0-1背包问题（Knapsack Problem）、装箱问题（Bin Packing Problem）、图着色问题（Graph Coloring Problem）、聚类问题（Clustering Problem）等。这些问题描述非常简单，并且有很强的工程代表性，但最优化求解很困难，其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间，以致根本不可能在现有计算机上实现，即所谓的“组合爆炸”。正是这些问题的代表性和复杂性激起了人们对组合优化理论与算法的研究兴趣。

5. 组合优化的问题分类

典型的组合优化问题有：
旅行商问题（Traveling Salesman Problem－TSP）；
加工调度问题（Scheling Problem，如Flow-Shop，Job-Shop）；
0-1背包问题（Knapsack Problem）；
装箱问题（Bin Packing Problem）；
图着色问题（Graph Coloring Problem）；
聚类问题（Clustering Problem）等。
这些问题描述非常简单，并且有很强的工程代表性，但最优化求解很困难，其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间，以致根本不可能在现有计算机上实现，即所谓的“组合爆炸”。正是这些问题的代表性和复杂性激起了人们对组合优化理论与算法的研究兴趣。

6. 组合优化问题是不是只能用智能优化算法来解决有没有其它算法来解决这个问题

最优化算法，例如分枝定界、分枝定价、列生成、动态规划等算法也可以求解组合优化问题。

7. 连续优化问题和组合优化问题在算法设计方面的差异

这个问题本身不完整埃 组合数量最少这个优化目标有问题。按照题目理解，直接找出最少公共特性的最大集合就可以了。 聚类分析、神经网络等算法都可以做这种分类问题。

8. 使用matlab遗传算法工具箱能不能解决组合优化问题还有使用工具箱方便还是自己编程方便呢

1、要看你组合优化是属于哪种问题，一般的组合优化都是混合整数线性或非线性的，那么就不行了，因此要对遗传算法改进才能计算。
2、如果有现成的工具箱求解你的组合优化问题肯定要方便些，但碰到具体问题，可能要对参数进行一些设置更改，所以最好能有编程基础，那样就可以自己修改工具箱里面的参数或策略了

对你的补充问题，组合优化问题一般都是用matlab 和 lingo实现吧。建议买一本数学建模的书看一看，都涉及到组合优化问题，也可以下载论文看看。lingo对编程要简单些，主要是求混合规划，缺点是似乎还不能用上多目标问题，一般的组合优化都属于多目标问题。但是matlab功能强大的多。

9. 经典组合优化问题的一般求解方法有哪些

组合最优化方法(combinatorial optimizationmethod )求解组合最优化问题的方法一般地，对于不同类的组合最优化问题，对应着不同的求解方法.判定一个组合最优化方法好坏的主要标准是运算次数.用n表示某一组合最优化问题的规模p(n)表示在对方法影响最坏的情况下所需的运算次数.若p(n)是n的多项式函数，则称该方法是多项式算法.凡能用多项式算法求解的问题都称为P问题.有一类问题称为NP完全问题，若这类组合最优化问题具有如下特点:
1.它们都未找到多项式算法.
2.如果对其中某一问题存在多项式算法，那么此类中的所有问题也都有多项式算法.
已发现有成千的组合最优化问题属于NP完成问题.为求解该类中的问题，人们往往采用“启发式”方法.这些方法一般地，不能保证求得问题的最优解，但常能得到较好的近似解