ma_model_preparation1

Posted on

math_modeling competition for 2019 preparation

abstract:

I'd like to record my preparation for this competition, including some tricks on coding, and comperhension on some important math models and algorithms. Also, I'd like to share some interesting tools we can use, such as Gephi, Citespace, and so on.
Meanwhile, I may record some basic knowledge on machine learning and data mining, even includes tensorflow and pytorch framework. So this series will be a hodgepodge of quite many things and knowledge. I hope I can truly learn something by doing so, and also help you work better.

part one

EA (Evolutionary Algorithms)

1. introduce

there are so many algorithms use the idea of evolution, and in the competition of math modeling, it’s so important that almost every time, we can slove a problem using it.

these algorithms include genetic algorithm, ant colony algorithm, Annealing Algorithm, neural network, tabu search and so on. I’d like to put focus on genetic algorithm this time, but I’ll also give some abstract on other algorithms. Also, codes will be shared on this website

2. genetic algorithm

1. 流程图(flow chart)

流程图

2.problem needs sloving
maxf(x1,x2) = 21.5+x1*sin(4*pi*x1)+x2*sin(20*pi*x2)

                     s.t. -3.0<=x1<=12.1

                            4.1<=x2<=5.8

so we’d like to slove this problem using genetic algorithm, to better understand the process of this great algorithm.

3.the big ideas

basic ideas:

  1. 适应度函数(to compute the performance)

    适应度函数能够有效帮助后续的选择过程，进行有条件的保留与选择，帮助进行有效的迭代
  2. 交叉(crossover)

    针对不同的问题有不同的交叉方式，在交叉过程中需要注意保持原有数据的真实性，不能出现超越规则之外的数据。通常，我们设置crossover rate=0.8，能够有效地帮助进行迭代，较快且较好地收敛
  3. 变异(mutation)

    我们一般设置mutation rete=1/L(L: len of vector)，变异能减少收敛到局部最优的可能性，使得整个算法有更好的优化性，能够得到较好的结果
  4. 选择(selection)

    选择是遗传算法中一个非常重要的步骤，通常，选择的方式有多种(including roulette wheel selection, rank selection, tournament selection and Elitism + Offspring selection )，根据不同的问题，采用不同的选择方式，能够得到较好的结果。在这个问题中，我们采用轮盘赌算法来进行选择（关于轮盘赌算法的讲解，你可以查看轮盘赌算法)
    4. the code on this problem
    you can find the code on my github repository MCM/ICM preparation, I save the python code on the floder learning_code.
    Because of the code is a little complicated, so maybe I’ll write down another blog or ipython to denote some details about this process.

other basic algorithms

1. 粒子群算法（蚁群算法）

在使用蚁群算法求解现实问题时，先生成具有一定数量蚂蚁的蚁群，让每一只蚂
蚁建立一个解或解的一部分，每只人工蚁从问题的初始状态出发，根据“激素”浓度来
选择下一个要转移到的状态，直到建立起一个解，每只蚂蚁根据所找到的解的好坏程度
在所经过的状态上释放与解的质量成正比例的“激素”。之后，每只蚂蚁又开始新的求
解过程，直到寻找到满意解。为避免停滞现象，引入了激素更新机制。

2. 遗传退火算法

模拟退火算法得益于材料的统计力学的研究成果。统计力学表明材料中粒子的不
同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和
重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这个过
程被称为退火），粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形
成处于低能状态的晶体。

在模拟退火算法中应注意以下问题：
（1）理论上，降温过程要足够缓慢，要使得在每一温度下达到热平衡。但在计算
机实现中，如果降温速度过缓，所得到的解的性能会较为令人满意，但是算法会太慢，
相对于简单的搜索算法不具有明显优势。如果降温速度过快，很可能最终得不到全局最
优解。因此使用时要综合考虑解的性能和算法速度，在两者之间采取一种折衷。
（2）要确定在每一温度下状态转换的结束准则。实际操作可以考虑当连续m 次的
转换过程没有使状态发生变化时结束该温度下的状态转换。最终温度的确定可以提前定
为一个较小的值e T ，或连续几个温度下转换过程没有使状态发生变化算法就结束。
（3）选择初始温度和确定某个可行解的邻域的方法也要恰当。

3. 禁忌搜索

禁忌搜索算法是组合优化算法的一种，是局部搜索算法的扩展。禁忌搜索算法是人
工智能在组合优化算法中的一个成功应用。禁忌搜索算法的特点是采用了禁忌技术。所
谓禁忌就是禁止重复前面的工作。禁忌搜索算法用一个禁忌表记录下已经到达过的局部
最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点。
禁忌搜索算法实现的技术问题是算法的关键。禁忌搜索算法涉及侯选集合、禁忌
对象、评价函数、特赦规则、记忆频率信息等概念。

4. 神经网络

由于神经网络有极大的用途，一般会用其来进行深度学习，所以如果有时间的话，我会更新关于深度学习的部分博客用以记录和交流，故神经网络在这里不再提及。

当然，对于神经网络的搭建，现在已经有许多开源的框架，我在后续的博客中将使用pytorch框架，并尝试使用fastai 来实现相关的一些项目。

5. all in all

我们已经看到了一个简单的遗传算法，就要使用上百行的python代码来实现，那么显然，既然在matlab 中有实现相关进化算法的框架，在python中同样也有，推荐的一个是geatpy。
你可以使用 

pip install geatpy

来安装它。同时，你也可以通过这个网站geatpy来学习具体的框架，希望它能帮助你更好地掌握进化算法。