13518219792
想象一下，您有一个线性方程组和不等式系统。这样的系统通常有许多可能的解决方案。线性规划是一组数学和计算工具，可让您找到该系统的特定解，该解对应于某些其他线性函数的最大值或最小值。
创新互联公司专注于七星网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供七星营销型网站建设，七星网站制作、七星网页设计、七星网站官网定制、小程序设计服务，打造七星网络公司原创品牌,更为您提供七星网站排名全网营销落地服务。
混合整数线性规划是 线性规划 的扩展。它处理至少一个变量采用离散整数而不是连续值的问题。尽管乍一看混合整数问题与连续变量问题相似，但它们在灵活性和精度方面具有显着优势。
整数变量对于正确表示自然用整数表示的数量很重要，例如生产的飞机数量或服务的客户数量。
一种特别重要的整数变量是 二进制变量 。它只能取 零 或 一 的值，在做出是或否的决定时很有用，例如是否应该建造工厂或者是否应该打开或关闭机器。您还可以使用它们来模拟逻辑约束。
线性规划是一种基本的优化技术，已在科学和数学密集型领域使用了数十年。它精确、相对快速，适用于一系列实际应用。
混合整数线性规划允许您克服线性规划的许多限制。您可以使用分段线性函数近似非线性函数、使用半连续变量、模型逻辑约束等。它是一种计算密集型工具，但计算机硬件和软件的进步使其每天都更加适用。
通常，当人们试图制定和解决优化问题时，第一个问题是他们是否可以应用线性规划或混合整数线性规划。
以下文章说明了线性规划和混合整数线性规划的一些用例：
随着计算机能力的增强、算法的改进以及更多用户友好的软件解决方案的出现，线性规划，尤其是混合整数线性规划的重要性随着时间的推移而增加。
解决线性规划问题的基本方法称为，它有多种变体。另一种流行的方法是。
混合整数线性规划问题可以通过更复杂且计算量更大的方法来解决，例如，它在幕后使用线性规划。这种方法的一些变体是，它涉及使用 切割平面 ，以及。
有几种适用于线性规划和混合整数线性规划的合适且众所周知的 Python 工具。其中一些是开源的，而另一些是专有的。您是否需要免费或付费工具取决于问题的规模和复杂性，以及对速度和灵活性的需求。
值得一提的是，几乎所有广泛使用的线性规划和混合整数线性规划库都是以 Fortran 或 C 或 C++ 原生和编写的。这是因为线性规划需要对（通常很大）矩阵进行计算密集型工作。此类库称为求解器。Python 工具只是求解器的包装器。
Python 适合围绕本机库构建包装器，因为它可以很好地与 C/C++ 配合使用。对于本教程，您不需要任何 C/C++（或 Fortran），但如果您想了解有关此酷功能的更多信息，请查看以下资源：
基本上，当您定义和求解模型时，您使用 Python 函数或方法调用低级库，该库执行实际优化工作并将解决方案返回给您的 Python 对象。
几个免费的 Python 库专门用于与线性或混合整数线性规划求解器交互：
在本教程中，您将使用SciPy和PuLP来定义和解决线性规划问题。
在本节中，您将看到线性规划问题的两个示例：
您将在下一节中使用 Python 来解决这两个问题。
考虑以下线性规划问题：
你需要找到X和Ÿ使得红色，蓝色和黄色的不平等，以及不平等X 0和ÿ 0，是满意的。同时，您的解决方案必须对应于z的最大可能值。
您需要找到的自变量（在本例中为 x 和 y ）称为 决策变量 。要最大化或最小化的决策变量的函数（在本例中为 z） 称为 目标函数 、 成本函数 或仅称为 目标 。您需要满足的 不等式 称为 不等式约束 。您还可以在称为 等式约束 的约束中使用方程。
这是您如何可视化问题的方法：
红线代表的功能2 X + Ý = 20，和它上面的红色区域示出了红色不等式不满足。同样，蓝线是函数 4 x + 5 y = 10，蓝色区域被禁止，因为它违反了蓝色不等式。黄线是 x + 2 y = 2，其下方的黄色区域是黄色不等式无效的地方。
如果您忽略红色、蓝色和黄色区域，则仅保留灰色区域。灰色区域的每个点都满足所有约束，是问题的潜在解决方案。该区域称为 可行域 ，其点为 可行解 。在这种情况下，有无数可行的解决方案。
您想最大化z。对应于最大z的可行解是 最优解 。如果您尝试最小化目标函数，那么最佳解决方案将对应于其可行的最小值。
请注意，z是线性的。你可以把它想象成一个三维空间中的平面。这就是为什么最优解必须在可行区域的 顶点 或角上的原因。在这种情况下，最佳解决方案是红线和蓝线相交的点，稍后您将看到。
有时，可行区域的整个边缘，甚至整个区域，都可以对应相同的z值。在这种情况下，您有许多最佳解决方案。
您现在已准备好使用绿色显示的附加等式约束来扩展问题：
方程式 x + 5 y = 15，以绿色书写，是新的。这是一个等式约束。您可以通过向上一张图像添加相应的绿线来将其可视化：
现在的解决方案必须满足绿色等式，因此可行区域不再是整个灰色区域。它是绿线从与蓝线的交点到与红线的交点穿过灰色区域的部分。后一点是解决方案。
如果插入x的所有值都必须是整数的要求，那么就会得到一个混合整数线性规划问题，可行解的集合又会发生变化：
您不再有绿线，只有沿线的x值为整数的点。可行解是灰色背景上的绿点，此时最优解离红线最近。
这三个例子说明了 可行的线性规划问题 ，因为它们具有有界可行区域和有限解。
如果没有解，线性规划问题是 不可行的 。当没有解决方案可以同时满足所有约束时，通常会发生这种情况。
例如，考虑如果添加约束x + y 1会发生什么。那么至少有一个决策变量（x或y）必须是负数。这与给定的约束x 0 和y 0相冲突。这样的系统没有可行的解决方案，因此称为不可行的。
另一个示例是添加与绿线平行的第二个等式约束。这两行没有共同点，因此不会有满足这两个约束的解决方案。
一个线性规划问题是 无界的 ，如果它的可行区域是无界，将溶液不是有限。这意味着您的变量中至少有一个不受约束，可以达到正无穷大或负无穷大，从而使目标也无限大。
例如，假设您采用上面的初始问题并删除红色和黄色约束。从问题中删除约束称为 放松 问题。在这种情况下，x和y不会在正侧有界。您可以将它们增加到正无穷大，从而产生无限大的z值。
在前面的部分中，您研究了一个与任何实际应用程序无关的抽象线性规划问题。在本小节中，您将找到与制造业资源分配相关的更具体和实用的优化问题。
假设一家工厂生产四种不同的产品，第一种产品的日产量为x ₁，第二种产品的产量为x 2，依此类推。目标是确定每种产品的利润最大化日产量，同时牢记以下条件：
数学模型可以这样定义：
目标函数（利润）在条件 1 中定义。人力约束遵循条件 2。对原材料 A 和 B 的约束可以从条件 3 和条件 4 中通过对每种产品的原材料需求求和得出。
最后，产品数量不能为负，因此所有决策变量必须大于或等于零。
与前面的示例不同，您无法方便地将其可视化，因为它有四个决策变量。但是，无论问题的维度如何，原理都是相同的。
在本教程中，您将使用两个Python 包来解决上述线性规划问题：
SciPy 设置起来很简单。安装后，您将拥有开始所需的一切。它的子包 scipy.optimize 可用于线性和非线性优化。
PuLP 允许您选择求解器并以更自然的方式表述问题。PuLP 使用的默认求解器是COIN-OR Branch and Cut Solver (CBC)。它连接到用于线性松弛的COIN-OR 线性规划求解器 (CLP)和用于切割生成的COIN-OR 切割生成器库 (CGL)。
另一个伟大的开源求解器是GNU 线性规划工具包 (GLPK)。一些著名且非常强大的商业和专有解决方案是Gurobi、CPLEX和XPRESS。
除了在定义问题时提供灵活性和运行各种求解器的能力外，PuLP 使用起来不如 Pyomo 或 CVXOPT 等替代方案复杂，后者需要更多的时间和精力来掌握。
要学习本教程，您需要安装 SciPy 和 PuLP。下面的示例使用 SciPy 1.4.1 版和 PuLP 2.1 版。
您可以使用pip以下方法安装两者：
您可能需要运行pulptest或sudo pulptest启用 PuLP 的默认求解器，尤其是在您使用 Linux 或 Mac 时：
或者，您可以下载、安装和使用 GLPK。它是免费和开源的，适用于 Windows、MacOS 和 Linux。在本教程的后面部分，您将看到如何将 GLPK（除了 CBC）与 PuLP 一起使用。
在 Windows 上，您可以下载档案并运行安装文件。
在 MacOS 上，您可以使用 Homebrew：
在 Debian 和 Ubuntu 上，使用apt来安装glpk和glpk-utils：
在Fedora，使用dnf具有glpk-utils：
您可能还会发现conda对安装 GLPK 很有用：
安装完成后，可以查看GLPK的版本：
有关详细信息，请参阅 GLPK 关于使用Windows 可执行文件和Linux 软件包进行安装的教程。
在本节中，您将学习如何使用 SciPy优化和求根库进行线性规划。
要使用 SciPy 定义和解决优化问题，您需要导入scipy.optimize.linprog()：
现在您已经linprog()导入，您可以开始优化。
让我们首先解决上面的线性规划问题：
linprog()仅解决最小化（而非最大化）问题，并且不允许具有大于或等于符号 ( ) 的不等式约束。要解决这些问题，您需要在开始优化之前修改您的问题：
引入这些更改后，您将获得一个新系统：
该系统与原始系统等效，并且将具有相同的解决方案。应用这些更改的唯一原因是克服 SciPy 与问题表述相关的局限性。
下一步是定义输入值：
您将上述系统中的值放入适当的列表、元组或NumPy 数组中：
注意：请注意行和列的顺序！
约束左侧和右侧的行顺序必须相同。每一行代表一个约束。
来自目标函数和约束左侧的系数的顺序必须匹配。每列对应一个决策变量。
下一步是以与系数相同的顺序定义每个变量的界限。在这种情况下，它们都在零和正无穷大之间：
此语句是多余的，因为linprog()默认情况下采用这些边界（零到正无穷大）。
注：相反的float("inf")，你可以使用math.inf，numpy.inf或scipy.inf。
最后，是时候优化和解决您感兴趣的问题了。你可以这样做linprog()：
参数c是指来自目标函数的系数。A_ub和b_ub分别与不等式约束左边和右边的系数有关。同样，A_eq并b_eq参考等式约束。您可以使用bounds提供决策变量的下限和上限。
您可以使用该参数method来定义要使用的线性规划方法。有以下三种选择：
linprog() 返回具有以下属性的数据结构：
您可以分别访问这些值：
这就是您获得优化结果的方式。您还可以以图形方式显示它们：
如前所述，线性规划问题的最优解位于可行区域的顶点。在这种情况下，可行区域只是蓝线和红线之间的绿线部分。最优解是代表绿线和红线交点的绿色方块。
如果要排除相等（绿色）约束，只需删除参数A_eq并b_eq从linprog()调用中删除：
解决方案与前一种情况不同。你可以在图表上看到：
在这个例子中，最优解是红色和蓝色约束相交的可行（灰色）区域的紫色顶点。其他顶点，如黄色顶点，具有更高的目标函数值。
您可以使用 SciPy 来解决前面部分所述的资源分配问题：
和前面的例子一样，你需要从上面的问题中提取必要的向量和矩阵，将它们作为参数传递给.linprog()，然后得到结果：
结果告诉您最大利润是1900并且对应于x ₁ = 5 和x ₃ = 45。在给定条件下生产第二和第四个产品是没有利润的。您可以在这里得出几个有趣的结论：
opt.statusis0和opt.successis True，说明优化问题成功求解，最优可行解。
SciPy 的线性规划功能主要用于较小的问题。对于更大和更复杂的问题，您可能会发现其他库更适合，原因如下：
幸运的是，Python 生态系统为线性编程提供了几种替代解决方案，这些解决方案对于更大的问题非常有用。其中之一是 PuLP，您将在下一节中看到它的实际应用。
PuLP 具有比 SciPy 更方便的线性编程 API。您不必在数学上修改您的问题或使用向量和矩阵。一切都更干净，更不容易出错。
像往常一样，您首先导入您需要的内容：
现在您已经导入了 PuLP，您可以解决您的问题。
您现在将使用 PuLP 解决此系统：
第一步是初始化一个实例LpProblem来表示你的模型：
您可以使用该sense参数来选择是执行最小化（LpMinimize或1，这是默认值）还是最大化（LpMaximize或-1）。这个选择会影响你的问题的结果。
一旦有了模型，就可以将决策变量定义为LpVariable类的实例：
您需要提供下限，lowBound=0因为默认值为负无穷大。该参数upBound定义了上限，但您可以在此处省略它，因为它默认为正无穷大。
可选参数cat定义决策变量的类别。如果您使用的是连续变量，则可以使用默认值"Continuous"。
您可以使用变量x和y创建表示线性表达式和约束的其他 PuLP 对象：
当您将决策变量与标量相乘或构建多个决策变量的线性组合时，您会得到一个pulp.LpAffineExpression代表线性表达式的实例。
注意：您可以增加或减少变量或表达式，你可以乘他们常数，因为纸浆类实现一些Python的特殊方法，即模拟数字类型一样__add__()，__sub__()和__mul__()。这些方法用于像定制运营商的行为+，-和*。
类似地，您可以将线性表达式、变量和标量与运算符 ==、=以获取表示模型线性约束的纸浆.LpConstraint实例。
注：也有可能与丰富的比较方法来构建的约束.__eq__()，.__le__()以及.__ge__()定义了运营商的行为==，=。
考虑到这一点，下一步是创建约束和目标函数并将它们分配给您的模型。您不需要创建列表或矩阵。只需编写 Python 表达式并使用+=运算符将它们附加到模型中：
在上面的代码中，您定义了包含约束及其名称的元组。LpProblem允许您通过将约束指定为元组来向模型添加约束。第一个元素是一个LpConstraint实例。第二个元素是该约束的可读名称。
设置目标函数非常相似：
或者，您可以使用更短的符号：
现在您已经添加了目标函数并定义了模型。
注意：您可以使用运算符将 约束或目标附加到模型中，+=因为它的类LpProblem实现了特殊方法.__iadd__()，该方法用于指定 的行为+=。
对于较大的问题，lpSum()与列表或其他序列一起使用通常比重复+运算符更方便。例如，您可以使用以下语句将目标函数添加到模型中：
它产生与前一条语句相同的结果。
您现在可以看到此模型的完整定义：
模型的字符串表示包含所有相关数据：变量、约束、目标及其名称。
注意：字符串表示是通过定义特殊方法构建的.__repr__()。有关 的更多详细信息.__repr__()，请查看Pythonic OOP 字符串转换：__repr__vs__str__ .
最后，您已准备好解决问题。你可以通过调用.solve()你的模型对象来做到这一点。如果要使用默认求解器 (CBC)，则不需要传递任何参数：
.solve()调用底层求解器，修改model对象，并返回解决方案的整数状态，1如果找到了最优解。有关其余状态代码，请参阅LpStatus[]。
你可以得到优化结果作为 的属性model。该函数value()和相应的方法.value()返回属性的实际值：
model.objective持有目标函数model.constraints的值，包含松弛变量的值，以及对象x和y具有决策变量的最优值。model.variables()返回一个包含决策变量的列表：
如您所见，此列表包含使用 的构造函数创建的确切对象LpVariable。
结果与您使用 SciPy 获得的结果大致相同。
注意：注意这个方法.solve()——它会改变对象的状态，x并且y！
您可以通过调用查看使用了哪个求解器.solver：
输出通知您求解器是 CBC。您没有指定求解器，因此 PuLP 调用了默认求解器。
如果要运行不同的求解器，则可以将其指定为 的参数.solve()。例如，如果您想使用 GLPK 并且已经安装了它，那么您可以solver=GLPK(msg=False)在最后一行使用。请记住，您还需要导入它：
现在你已经导入了 GLPK，你可以在里面使用它.solve()：
该msg参数用于显示来自求解器的信息。msg=False禁用显示此信息。如果要包含信息，则只需省略msg或设置msg=True。
您的模型已定义并求解，因此您可以按照与前一种情况相同的方式检查结果：
使用 GLPK 得到的结果与使用 SciPy 和 CBC 得到的结果几乎相同。
一起来看看这次用的是哪个求解器：
正如您在上面用突出显示的语句定义的那样model.solve(solver=GLPK(msg=False))，求解器是 GLPK。
您还可以使用 PuLP 来解决混合整数线性规划问题。要定义整数或二进制变量，只需传递cat="Integer"或cat="Binary"到LpVariable。其他一切都保持不变：
在本例中，您有一个整数变量并获得与之前不同的结果：
Nowx是一个整数，如模型中所指定。（从技术上讲，它保存一个小数点后为零的浮点值。）这一事实改变了整个解决方案。让我们在图表上展示这一点：
如您所见，最佳解决方案是灰色背景上最右边的绿点。这是两者的最大价值的可行的解决方案x和y，给它的最大目标函数值。
GLPK 也能够解决此类问题。
现在你可以使用 PuLP 来解决上面的资源分配问题：
定义和解决问题的方法与前面的示例相同：
在这种情况下，您使用字典 x来存储所有决策变量。这种方法很方便，因为字典可以将决策变量的名称或索引存储为键，将相应的LpVariable对象存储为值。列表或元组的LpVariable实例可以是有用的。
上面的代码产生以下结果：
如您所见，该解决方案与使用 SciPy 获得的解决方案一致。最有利可图的解决方案是每天生产5.0第一件产品和45.0第三件产品。
让我们把这个问题变得更复杂和有趣。假设由于机器问题，工厂无法同时生产第一种和第三种产品。在这种情况下，最有利可图的解决方案是什么？
现在您有另一个逻辑约束：如果x ₁ 为正数，则x ₃ 必须为零，反之亦然。这是二元决策变量非常有用的地方。您将使用两个二元决策变量y ₁ 和y ₃，它们将表示是否生成了第一个或第三个产品：
除了突出显示的行之外，代码与前面的示例非常相似。以下是差异：
这是解决方案：
事实证明，最佳方法是排除第一种产品而只生产第三种产品。
就像有许多资源可以帮助您学习线性规划和混合整数线性规划一样，还有许多具有 Python 包装器的求解器可用。这是部分列表：
其中一些库，如 Gurobi，包括他们自己的 Python 包装器。其他人使用外部包装器。例如，您看到可以使用 PuLP 访问 CBC 和 GLPK。
您现在知道什么是线性规划以及如何使用 Python 解决线性规划问题。您还了解到 Python 线性编程库只是本机求解器的包装器。当求解器完成其工作时，包装器返回解决方案状态、决策变量值、松弛变量、目标函数等。
一、遗传算法介绍
遗传算法是通过模拟大自然中生物进化的历程，来解决问题的。大自然中一个种群经历过若干代的自然选择后，剩下的种群必定是适应环境的。把一个问题所有的解看做一个种群，经历过若干次的自然选择以后，剩下的解中是有问题的最优解的。当然，只能说有最优解的概率很大。这里，我们用遗传算法求一个函数的最大值。
f(x) = 10 * sin( 5x ) + 7 * cos( 4x ), 0 = x = 10
1、将自变量x进行编码
取基因片段的长度为10, 则10位二进制位可以表示的范围是0到1023。基因与自变量转变的公式是x = b2d(individual) * 10 / 1023。构造初始的种群pop。每个个体的基因初始值是[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]
2、计算目标函数值
根据自变量与基因的转化关系式，求出每个个体的基因对应的自变量，然后将自变量代入函数f（x），求出每个个体的目标函数值。
3、适应度函数
适应度函数是用来评估个体适应环境的能力，是进行自然选择的依据。本题的适应度函数直接将目标函数值中的负值变成0. 因为我们求的是最大值，所以要使目标函数值是负数的个体不适应环境，使其繁殖后代的能力为0.适应度函数的作用将在自然选择中体现。
4、自然选择
自然选择的思想不再赘述，操作使用轮盘赌算法。其具体步骤：
假设种群中共5个个体，适应度函数计算出来的个体适应性列表是fitvalue = [1 ,3, 0, 2, 4] ，totalvalue = 10 ， 如果将fitvalue画到圆盘上，值的大小表示在圆盘上的面积。在转动轮盘的过程中，单个模块的面积越大则被选中的概率越大。选择的方法是将fitvalue转化为[1 ， 4 ，4 , 6 ，10], fitvalue / totalvalue = [0.1 , 0.4 , 0.4 , 0.6 , 1.0] . 然后产生5个0-1之间的随机数，将随机数从小到大排序，假如是[0.05 , 0.2 , 0.7 , 0.8 ,0.9]，则将0号个体、1号个体、4号个体、4号个体、4号个体拷贝到新种群中。自然选择的结果使种群更符合条件了。
5、繁殖
假设个体a、b的基因是
a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
这两个个体发生基因交换的概率pc = 0.6.如果要发生基因交换，则产生一个随机数point表示基因交换的位置，假设point = 4,则：
a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
交换后为：
a = [1, 0, 0, 0, 1, 0, 1, 1, 1, 1]
b = [0, 0, 0, 1, 0, 1, 1, 1, 0, 0]
6、突变
遍历每一个个体，基因的每一位发生突变（0变为1,1变为0）的概率为0.001.突变可以增加解空间
二、代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def b2d(b): #将二进制转化为十进制 x∈[0,10] t = 0 for j in range(len(b)): t += b[j] * (math.pow(2, j)) t = t * 10 / 1023 return tpopsize = 50 #种群的大小#用遗传算法求函数最大值：#f(x)=10*sin(5x)+7*cos(4x) x∈[0,10]chromlength = 10 #基因片段的长度pc = 0.6 #两个个体交叉的概率pm = 0.001; #基因突变的概率results = [[]]bestindividual = []bestfit = 0fitvalue = []tempop = [[]]pop = [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1] for i in range(popsize)]for i in range(100): #繁殖100代 objvalue = calobjvalue(pop) #计算目标函数值 fitvalue = calfitvalue(objvalue); #计算个体的适应值 [bestindividual, bestfit] = best(pop, fitvalue) #选出最好的个体和最好的函数值 results.append([bestfit,b2d(bestindividual)]) #每次繁殖，将最好的结果记录下来 selection(pop, fitvalue) #自然选择，淘汰掉一部分适应性低的个体 crossover(pop, pc) #交叉繁殖 mutation(pop, pc) #基因突变 results.sort() print(results[-1]) #打印函数最大值和对应的
来自CODE的代码片
GA.py
1
2
3
4
5
6
7
8
9
def best(pop, fitvalue): #找出适应函数值中最大值，和对应的个体 px = len(pop) bestindividual = [] bestfit = fitvalue[0] for i in range(1,px): if(fitvalue[i] bestfit): bestfit = fitvalue[i] bestindividual = pop[i] return [bestindividual, bestfit]
来自CODE的代码片
best.py
1
2
3
4
5
6
7
8
9
10
11
def calfitvalue(objvalue):#转化为适应值，目标函数值越大越好，负值淘汰。 fitvalue = [] temp = 0.0 Cmin = 0; for i in range(len(objvalue)): if(objvalue[i] + Cmin 0): temp = Cmin + objvalue[i] else: temp = 0.0 fitvalue.append(temp) return fitvalue
来自CODE的代码片
calfitvalue.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import mathdef decodechrom(pop): #将种群的二进制基因转化为十进制（0,1023） temp = []; for i in range(len(pop)): t = 0; for j in range(10): t += pop[i][j] * (math.pow(2, j)) temp.append(t) return tempdef calobjvalue(pop): #计算目标函数值 temp1 = []; objvalue = []; temp1 = decodechrom(pop) for i in range(len(temp1)): x = temp1[i] * 10 / 1023 #（0,1023）转化为 （0,10） objvalue.append(10 * math.sin(5 * x) + 7 * math.cos(4 * x)) return objvalue #目标函数值objvalue[m] 与个体基因 pop[m] 对应
来自CODE的代码片
calobjvalue.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import randomdef crossover(pop, pc): #个体间交叉，实现基因交换 poplen = len(pop) for i in range(poplen - 1): if(random.random() pc): cpoint = random.randint(0,len(pop[0])) temp1 = [] temp2 = [] temp1.extend(pop[i][0 : cpoint]) temp1.extend(pop[i+1][cpoint : len(pop[i])]) temp2.extend(pop[i+1][0 : cpoint]) temp2.extend(pop[i][cpoint : len(pop[i])]) pop[i] = temp1 pop[i+1] = temp2
来自CODE的代码片
crossover.py
1
2
3
4
5
6
7
8
9
10
11
12
13
import randomdef mutation(pop, pm): #基因突变 px = len(pop) py = len(pop[0]) for i in range(px): if(random.random() pm): mpoint = random.randint(0,py-1) if(pop[i][mpoint] == 1): pop[i][mpoint] = 0 else: pop[i][mpoint] = 1
来自CODE的代码片
mutation.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import randomdef sum(fitvalue): total = 0 for i in range(len(fitvalue)): total += fitvalue[i] return totaldef cumsum(fitvalue): for i in range(len(fitvalue)): t = 0; j = 0; while(j = i): t += fitvalue[j] j = j + 1 fitvalue[i] = t;def selection(pop, fitvalue): #自然选择（轮盘赌算法） newfitvalue = [] totalfit = sum(fitvalue) for i in range(len(fitvalue)): newfitvalue.append(fitvalue[i] / totalfit) cumsum(newfitvalue) ms = []; poplen = len(pop) for i in range(poplen): ms.append(random.random()) #random float list ms ms.sort() fitin = 0 newin = 0 newpop = pop while newin poplen: if(ms[newin] newfitvalue[fitin]): newpop[newin] = pop[fitin] newin = newin + 1 else: fitin = fitin + 1 pop = newpop
Python是工具 数据挖掘是研究方向 数据挖掘有很多经典算法，这些算法有的有现成Python包，你可以用Python调用这些包处理自己的数据实现数据挖掘。
Python通常是直接从数据库取出已有信息，进行一些统计、可视化、文字结论等。数据挖掘一般是指从大量的数据中通过算法搜索隐藏于其中信息的过程。
数据挖掘只能告诉你，A和B可能存在相关关系，但是它无法告诉你A和B存在什么相关关系。机器学习是从假设空间H中寻找假设函数g近似目标函数f。数据挖掘是从大量的数据中寻找数据相互之间的特性。主要挖掘方法有:分类、估计、预测、相关性分组或关联规则、聚类、复杂数据类型挖掘(Text, Web ,图形图像，视频，音频等)等技术。
想要了解更多有关数据挖掘的信息，可以了解一下CDA数据分析师的课程。CDA数据分析师证书的含金量是很高的，课程内容兼顾培养解决数据挖掘流程问题的横向能力以及解决数据挖掘算法问题的纵向能力。帮助学员掌握真正过硬的解决业务问题的数据挖掘能力。点击预约免费试听课。
这篇的内容是一系列针对在Python中从零开始运用机器学习能力工作流的辅导第一部分，覆盖了从小组开始的算法编程和其他相关工具。最终会成为一套手工制成的机器语言工作包。这次的内容会首先从数据准备开始。
—— 来自Matthew Mayo, KDnuggets
似乎大家对机器学习能力的认知总是简单到把一系列论据传送到越来越多的数据库和应用程序界面中，接着就期待能有一些神奇的结果出现。可能你对在这些数据库里究竟发生了什么有自己很好的理解—— 从数据准备到建模到结果演示呈现等等，但不得不说你依然需要依赖于这些纷繁的工具去完成自己的工作。
这其实很正常。我们用被准确检验证明过能运行的工具来完成一些日常的任务是无可厚非的。重新发明使用那些不能有效滚动的轮子不是最好的办法。这样会有很多局限，也会浪费很多的不必要的时间。无论你是使用开放源代码还是被授权的工具来完成你工作，这些代码工具已经被很多人反复试用升级以确保当你上手使用的时候能够以最好的质量完成你的工作。
然而，有些苦活累活你自己做也是有价值的，即便是作为一种教育性的努力。我不是要推荐你们从零开始通过自己深度学习练习写出一个程序框架，至少不能一直这样，但哪怕只有一次通过不断的试验和失败，从头开始写出和自己的算实现它们的支持工具也是非常好的。我可能说的不对，但我认为如今在学习机器学习能力、数据科学、人工智能等方面的大多数人都没有在这么做。
所以让我们从头开始，来学习在Python里建立一些机器学习能力的相关知识。
“From Scratch” 究竟是什么意思？
首先，我先申明：当我提到“From Scratch”，我的意思是尽可能少的借助外界的帮助。当然这也是相对的，但是为了达成我们的目标，我会划定界限，当我们在写自己的矩阵模型、数据框或者构建自己的数据库时，我们会分别使用Python中的numpy、panda和matplotlib库。在某些情况下，我们甚至不会使用这些库的全部功能。我们稍后会讨论，让我们先暂时放一放它们的名字以便大家更好的理解。在Python自带的库中自带的功能原则上都是可以使用的，但除此之外，我们就要自己来写了。
我们需要从一个点入手，那就让我们从一些简单的数据准备任务开始吧。开始的时候我们会慢一点，但当我们对（要学习的东西）有了一点感觉以后，我们会逐渐加快速度。除了数据准备，我们还需要数据转换、结果演示和呈现工具——更不必说机器学习能力算法了——来达成我们我们即将要完成的目标。
我们的想法是手动拼接任何我们需要的重大功能，以便完成我们的机器学习能力任务。当序列展开的时候，我们可以添加新的工具和算法，同时我们也能重新思考我们以前的假设（是否正确），使整个过程尽可能重复迭代，就像它会渐近一样。慢慢的，我们会集中精力在我们的目标上，制定策略来完成目标，把它们运用到Python里，再检验它们是否能够运行。
最终的结果，就想我们现在预期的一样，会是有序排列在我们自己的简易的机器学习数据库中的一系列简单的Python模型。对于初学者，我相信这是理解机器学习过程、工作流和算法如何运行的非常宝贵的经验。
工作流（workflow）究竟是什么意思？
工作流对不同的人意味着不同的意思，但是我们这里说的工作流指的是机器学习项目中的一部分。我们有很多过程框架来帮助我们追踪我的工作进程，但现在让我们简化到一下的这些：
获取数据
处理/准备数据
建立模型
解释呈现结果
在我们真正做的时候我们可以拓展，但是这是我们现在自己设计的简单的机器学习的过程框架。同时，“输送管（小箭头）”暗含了把工作流中各功能聚集在一起的能力，所以让我们把这些记住然后继续向前。
获得数据
在我们建立自己的模型之前，我们需要一些数据，还需要确认这些数据与我们合理的期望相符合。为了检测的目的（而不是训练或测试，但只是测试我们自己的设备），我们会使用虹膜数据集，你可以从这里下载。尽管我们可以在网上找到很多版本的数据集，但我建议我们都使用相同的原始数据，以确保我们的准备工作正常运行。
让我们来看一看：
既然我们已经知道了这个简单的数据集和它对应的文件，我们先来想一想我们需要做什么使原始数据演变成我们想要的结果：
数据需要储存成CSV格式的文件
实例大部分由有数字属性的值组成
组别是经过分组的内容
到目前为止，以上没有一种是对所有的数据集都适用的，但是也没有任何一个是只能适用于某一种数据集的。这使得我们能够有机会编写我们可以以后重复使用的代码。好的编程练习会让我们集中于重复利用性和模块性。
一些简单的探索性数据分析被罗列如下：
(上图为具体数值，下图为图像化数据)
准备数据
虽然数据准备在我们现在这个特定的情境中需要的很少，但是有时还是会需要。尤其是我们需要确认我们解释了标题行，去除了任何pandas呈现出来的参数，并且把我们的每一次组的值从名字型的转化成数值型的。因为在我们使用模型时已经没有名字性数值了，所以到此为止至少就没有更复杂的转化了。
最终，我们也需要一个对我们自己的算法的更好的数据呈现，所以我们在继续向前进行之前会确保我们最终呈现的是一个矩阵——或者numpy nadarry。我们的数据准备工作流接下来会做一下的表格：
同时，我们需要主要我们没有理由相信所有有趣的数据都会被储存在被逗号分开的文件里。我们可能希望能够从一个SQL数据库里或者直接从网上获取数据，从这两个地方找到的数据我们以后还能返回去回看。
首先，让我们写一个简单的函数，把一个CSV文件上传到DataFrame。当然，这在内网做很容易，但是再往前想一步我们可能想再加一些额外的步骤到我们自己的数据集里以便我们以后上载函数。
这个编码是相当直接的。一行一行的读数据文件就完成了一些额外的预先加工，比如忽略了那些内容非数据的行（我们认为在数据文件中评价是由井号键开始的，尽管这很荒谬。）我们可以详细说明这个数据集文件是否包括标题，我们也可以接受csv和tsv文件，csv文件是默认的设置。
有一些错误检查存在，但它还并不是很健全，所以我们或许可以晚一点再回来说这个话题。此外，逐条读文件再逐条决定要对这些行做什么，比直接用内置功能把处理干净的一致的cs一文件直接读到DataFrame中要慢，但权衡之后我们发现允许更多的灵活性，在这一阶段是值得的（但读大的文件可能会发花费很久的时间）。不要忘了，如果一部分内置操作不是最好的方法，我们可以晚一些再做调整。
在我们尝试运行自己的编码之前，我们需要来写一个函数，把名字类数值转化成数字类数值。为了推广函数，我们需要使它能够用于数据集中的任何属性的数值，不仅仅是运用于不同的类别。我们还应该跟踪属性名称最终是否成为了整数。有了之前把csv或ts me的数据文件上传pandas的DataFrame的步骤经验，这个函数应该同时接受一个pandas DataFrames以及被转化为数字的属性名称。
我们还要注意，我们回避了关于使用单热编码的话题，这涉及到分类的非分类属性，但我认为我们以后还会回到这个话题。
上述的函数又是一个简单的，但是能帮助我们完成目标函数。我们可以用很多不同的方式来完成这个任务，包括使用pandas内置的功能，但是让你从一些会让你有些累的苦差事开始做就是这个函数的意义。
现在我们可以从文件中加载一个数据集，然后把分类属性值转换成数字属性值（我们也可以保留这些映像在字典中供以后使用）。就像之前提到的，我们希望我们的数据集最终是以numpy ndarry的形式存在，这样我们可以在自己的算法中很简单的使用。同样的，这是一个简单的任务，但写一个函数会让我们在以后需要的时候还可以以此为准。
即使以前任何的功能都没有过度的杀伤力，但这个功能有可能有。但请忍耐我，我们遵守非常全面的编程准则--如果过于谨慎的话。在我们继续往下讲的过程中会有很好的机会让我们对已有的功能做改变或添加。这些变化如果能在一个地方实施并且记录在案，从长远来看非常有意义。
测试数据准备的工作流
我们的工作流迄今为止可能仍然是构建板块的形式，但让我们给自己的编码一个测试。
我们的代码正在按我们希望的方式工作，让我们做一些简单的房屋清理工作。一旦开始滚动，我们将为我们的编码提供一个更全面的组织结构，但是现在我们需要把所有这些功能加到一个单独的文件中，并保存成为dataset.py的格式。这会让我们以后的使用更方便，下次我们会学到。
未来计划
之后我们会学习简单的分类算法，k最近邻算法。我们会学习如何在简单的工作流中构建分类和聚类模型。毫无疑问，这需要编写一些限额外的工具来帮助我们完成项目，并且我确定我们还将对已经做完的部分进行修改。
练习机器学习就是理解机器学习的最好方法。运用我们的工作流中需要的算法和支持工具最终会被证明是有用的。
python的内置函数（68个）
Python考核31个内置函数，
python内置了很多内置函数、类方法属性及各种模块。当我们想要当我们想要了解某种类型有哪些属性方法以及每种方法该怎么使用时，我们可以使用dir()函数和help()函数在python idle交互式模式下获得我们想要的信息。
• dir()函数获得对象中可用属性的列表
Python中的关键词有哪些？
dir(__builtins__)：查看python内置函数
help(‘keywords‘)：查看python关键词
如微分积分方程的求解程序、访问互联网、获取日期和时间、机器学习算法等。这些程序往往被收入程序库中，构成程序库。
只有经过严格检验的程序才能放在程序库里。检验，就是对程序作充分的测试。通常进行的有正确性测试、精度测试、速度测试、边界条件和出错状态的测试。经过检验的程序不但能保证计算结果的正确性，而且对错误调用也能作出反应。程序库中的程序都是规范化的。所谓规范化有三重含义：①同一库里所有程序的格式是统一的；② 对这些程序的调用方法是相同的；③ 每个程序所需参数的数目、顺序和类型都是严格规定好的。
Python的库包含标准库和第三方库
标准库：程序语言自身拥有的库，可以直接使用。help('modules')
第三方库：第三方者使用该语言提供的程序库。
标准库： turtle 库（必选）、 random 库（必选）、 time 库（可选）。
• turtle 库：图形绘制库
原理如同控制一只海龟，以不同的方向和速度进行位移而得到其运动轨迹。
使用模块的帮助时，需要先将模块导入。
例如：在IDLE中输入import turtle
dir(turtle)
help(turtle.**)
1.画布
画布就是turtle为我们展开用于绘图区域, 我们可以设置它的大小和初始位置。
setup()方法用于初始化画布窗口大小和位置，参数包括画布窗口宽、画布窗口高、窗口在屏幕的水平起始位置和窗口在屏幕的垂直起始位置。
参数:width, height: 输入宽和高为整数时,表示 像素 ;为小数时,表示占据电脑屏幕的比例。(startx,starty):这一坐标表示
矩形窗口左上角顶点的位置,如果为空,则窗口位于屏幕中心:
例如：setup(640,480,300,300)表示在桌面屏幕(300,300)位置开始创建640×480大小的画布窗体。
2、画笔
• color() 用于设置或返回画笔颜色和填充颜色。
例如：color(‘red’)将颜色设为红色，也可用fillcolor()方法设置或返回填充颜色，或用pencolor()方法设置或返回笔触颜色。
基于以下三个原因，我们选择Python作为实现机器学习算法的编程语言：(一) Python的语法清晰；(二) 易于操作纯文本文件；(三) 使用广泛，存在大量的开发文档。 可执行伪代码 Python具有清晰的语法结构，大家也把它称作可执行伪代码（executable pseudo-code）。默认安装的Python开发环境已经附带了很多高级数据类型，如列表、元组、字典、集合、队列等，无需进一步编程就可以使用这些数据类型的操作。使用这些数据类型使得实现抽象的数学概念非常简单。此外，读者还可以使用自己熟悉的编程风格，如面向对象编程、面向过程编程、或者函数式编程。不熟悉Python的读者可以参阅附录A，该附录详细介绍了Python语言、Python使用的数据类型以及安装指南。 Python语言处理和操作文本文件非常简单，非常易于处理非数值型数据。Python语言提供了丰富的正则表达式函数以及很多访问Web页面的函数库，使得从HTML中提取数据变得非常简单直观。 Python比较流行 Python语言使用广泛，代码范例也很多，便于读者快速学习和掌握。此外，在开发实际应用程序时，也可以利用丰富的模块库缩短开发周期。 在科学和金融领域，Python语言得到了广泛应用。SciPy和NumPy等许多科学函数库都实现了向量和矩阵操作，这些函数库增加了代码的可读性，学过线性代数的人都可以看懂代码的实际功能。另外，科学函数库SciPy和NumPy使用底层语言（C和Fortran）编写，提高了相关应用程序的计算性能。本书将大量使用Python的NumPy。 Python的科学工具可以与绘图工具Matplotlib协同工作。Matplotlib可以绘制二D、三D图形，也可以处理科学研究中经常使用到的图形，所以本书也将大量使用Matplotlib。 Python开发环境还提供了交互式shell环境，允许用户开发程序时查看和检测程序内容。 Python开发环境将来还会集成Pylab模块，它将NumPy、SciPy和Matplotlib合并为一个开发环境。在本书写作时，Pylab还没有并入Python环境，但是不远的将来我们肯定可以在Python开发环境找到它。 Python语言的特色 诸如MATLAB和Mathematica等高级程序语言也允许用户执行矩阵操作，MATLAB甚至还有许多内嵌的特征可以轻松地构造机器学习应用，而且MATLAB的运算速度也很快。然而MATLAB的不足之处是软件费用太高，单个软件授权就要花费数千美元。虽然也有适合MATLAB的第三方插件，但是没有一个有影响力的大型开源项目。 Java和C等强类型程序设计语言也有矩阵数学库，然而对于这些程序设计语言来说，最大的问题是即使完成简单的操作也要编写大量的代码。程序员首先需要定义变量的类型，对于Java来说，每次封装属性时还需要实现getter和setter方法。另外还要记着实现子类，即使并不想使用子类，也必须实现子类方法。为了完成一个简单的工作，我们必须花费大量时间编写了很多无用冗长的代码。Python语言则与Java和C完全不同，它清晰简练，而且易于理解，即使不是编程人员也能够理解程序的含义，而Java和C对于非编程人员则像天书一样难于理解。 所有人在小学二年级已经学会了写作，然而大多数人必须从事其他更重要的工作。 ——鲍比·奈特 也许某一天，我们可以在这句话中将“写作”替代为“编写代码”，虽然有些人对于编写代码很感兴趣，但是对于大多数人来说，编程仅是完成其他任务的工具而已。Python语言是高级编程语言，我们可以花费更多的时间处理数据的内在含义，而无须花费太多精力解决计算机如何得到数据结果。Python语言使得我们很容易表达自己的目的。 Python语言的缺点 Python语言唯一的不足是性能问题。Python程序运行的效率不如Java或者C代码高，但是我们可以使用Python调用C编译的代码。这样，我们就可以同时利用C和Python的优点，逐步地开发机器学习应用程序。我们可以首先使用Python编写实验程序，如果进一步想要在产品中实现机器学习，转换成C代码也不困难。如果程序是按照模块化原则组织的，我们可以先构造可运行的Python程序，然后再逐步使用C代码替换核心代码以改进程序的性能。C++ Boost库就适合完成这个任务，其他类似于Cython和PyPy的工具也可以编写强类型的Python代码，改进一般Python程序的性能。 如果程序的算法或者思想有缺陷，则无论程序的性能如何，都无法得到正确的结果。如果解决问题的思想存在问题，那么单纯通过提高程序的运行效率，扩展用户规模都无法解决这个核心问题。从这个角度来看，Python快速实现系统的优势就更加明显了，我们可以快速地检验算法或者思想是否正确，如果需要，再进一步优化代码
