随机搜索

利用随机数求极小点而求得函数近似的最优解的方法。变量允许的变化区间，不断随机地而不是有倾向性产生随机点，并计算其约束函数和目标函数的值，对满足约束条件的点，逐个比较其目标函数的值，将坏的点抛弃，保留好的点，最后便得到最优解的近似解。这种方法是建立在概率论的基础上，所取随机点越多，则得到最优解的概率也就越大。由于大多数计算机程序库中有随机数发生器，所以应用这种方法是很方便的。但是其计算精度较差、效率较低。随机搜索一般用于粗选或普查。常用的方法有随机跳跃法，随机走步法等。

http://baike.baidu.com/view/1587541.htm

Hill Clibming

It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by?incrementally?changing a single element of the solution. If the change produces a better solution, an incremental change is made to the new solution, repeating until no further improvements can be found.

The relative simplicity of the algorithm makes it a popular first choice amongst optimizing algorithms.

Hill climbing can often produce a better result than other algorithms when the amount of time available to perform a search is limited, such as with real-time systems. It is an?anytime algorithm: it can return a valid solution even if it's interrupted at any time before it ends.

It’s clear that simply moving down the slope will not necessarily lead?to the best solution overall. The final solution will be a local minimum, a solution
better than those around it but not the best overall. The best overall is called the?global minimum, which is what optimization algorithms are ultimately supposed to?find. One approach to this dilemma is called random-restart hill climbing, where the?hill climbing algorithm is run several times with random starting points in the hope?that one of them will be close to the global minimum.

模拟退火

退火（Annealing）在冶金学或材料工程中，是一种改变材料微结构且进而改变如硬度和强度等机械性质的热处理。

过程为将金属加温到某个高于再结晶温度的一点并维持此温度一段时间，再将其缓慢冷却。退火的功用在于恢复因冷加工而降低的性质，增加柔软性、延性和韧性，并释放内部残留应力、以及产生特定的显微结构。退火过程中，多以原子或晶格空位的移动释放内部残留应力，透过这些原子重组的过程来消除金属或陶瓷中的差排，然而这项改变动也让金属中的差排更易移动，增加了它们的延性。

模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis^[1]等人于1953年提出。1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。

http://baike.baidu.com/view/18185.htm

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。

模拟退火算法的模型

模拟退火算法的步骤

Genetic Algorithm

得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。

These work by initially creating a set of random solutions known as the
population. At each step of the optimization, the cost function for the entire population
is calculated to get a ranked list of solutions.

SolutionCost
[7, 5, 2, 3, 1, 6, 1, 6, 7, 1, 0, 3] 4394
[7, 2, 2, 2, 3, 3, 2, 3, 5, 2, 0, 8] 4661
… …
[0, 4, 0, 3, 8, 8, 4, 4, 8, 5, 6, 1] 7845
[5, 8, 0, 2, 8, 8, 8, 2, 1, 6, 6, 8] 8088