数学建模典型模型与算法-遗传算法

数学建模典型模型与算法-遗传算法 数学建模是研究和解决实际问题的数学方法和技术的总称。遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的 J.Holland 教授 1975 年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。 遗传算法的基本过程包括： 1. 初始化：设置进化代数计数器 t=0，设置最大进化代数 T，随机生成 M 个个体作为初始群体 P(0)。 2. 个体评价：计算群体 P(t)中各个个体的适应度。 3. 选择运算：将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。 4. 交叉运算：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。 5. 变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。 6. 终止条件判断：若 t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。 遗传算法的特点包括： 1. 遗传算法从问题解的串集开始搜索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。 2. 遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。 3. 遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。 4. 遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。 5. 具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。 遗传算法已经被广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域，是现代有关智能计算中的关键技术。 在数学建模中，遗传算法可以用于解决复杂的优化问题，例如函数最大值或最小值的问题。这种问题可以用数学规划模型来描述，即： max/min f(x) s.t. g(x) ≤ 0 h(x) = 0 x ∈ U 其中 x 是决策变量，f(x) 是目标函数，g(x) ≤ 0 和 h(x) = 0 是约束条件，U 是基本空间。 遗传算法是一种强有力的优化算法，具有广泛的应用前景和发展潜力。