暂时未有相关云产品技术能力~
-
发表了文章 2022-04-23
开源线性规划求解器（Linear Programming solver）LP_Solve和CLP的PK
01 Introduction前几天老板让测一下一些open source LP solver的稳定性。先看看本次上场的主角：lp_solve is a free (see LGPL for the GNU lesser general public license) linear (integer) programming solver based on the revised simplex method and the Branch-and-bound method for the integers. http://web.mit.edu/lpsolve/doc/Clp (Coin-or linear programming) is an open-source linear programming solver. It is primarily meant to be used as a callable library, but a basic, stand-alone executable version is also available. It is designed to find solutions of mathematical optimization problems of the form. https://github.com/coin-or/clpCPLEX Optimizer provides flexible, high-performance mathematical programming solvers for linear programming, mixed integer programming, quadratic programming and quadratically constrained programming problems. These solvers include a distributed parallel algorithm for mixed integer programming to leverage multiple computers to solve difficult problems.CPLEX可不是open-source的哦，这里主要是作为baseline，这样就可以看看lp_solve和Clp跟目前state of the art commercial solver的差距了。02 Setting开始之前，还是先做一些准备工作。首先是测试数据集，本次测试了两个数据集：NETLIB (91 cases) : http://www.netlib.org/lp/data/index.htmlL1 (34 cases) : http://www-eio.upc.edu/~jcastro/mindist_sdc.html数据集中的文件有些是.mps，部分solver可以直接读取。而NETLIB中的是compressed MPS，需要用他提供的工具进行解压。当然也可以从这里下载现成的：https://github.com/zrjer/LP-TEST-PROBLEM-FROM-NETLIB/tree/master/netlib_mps测试平台是ubuntu 18.04，lp_solve和clp用的是python调用，而CPLEX还是用Java调用的（别问，问就是使起来顺手），反正这些平台只是起到一个调用的作用，应该不会影响求解的时间（I think so~错了麻烦多多指正）。然后讲讲python下怎么配置lp_solve和clp吧：lp_solvewindows平台：直接到 https://www.lfd.uci.edu/~gohlke/pythonlibs/#lp_solve 这里下载对应版本的轮子然后pip进行安装，注意版本对应。linux平台：用conda安装，参考这里 https://anaconda.org/conda-forge/lpsolve55ClpClp是一个solver，Coin-or团队又为python开发了一个包叫CyLP（https://github.com/coin-or/CyLP） ，可以直接用来调用他们家的求解器 (CLP, CBC, and CGL)，所以下面讲讲怎么装CyLP。windows平台：直接pip install cylp，会自动安装clp等求解器。linux平台：比较麻烦，需要用conda先安装cbc等求解器，具体方法参照CyLP的说明，比较麻烦。然后把测试的code准备好，再写个shell脚本进行批量测试：dir=MPS_Files for file in $dir/*; do python lpsolve_run.py $file done意思是读取中的所有文件，然后挨个传入code里面让他跑，当然跑完了记得在程序中把一些结果记录一下哦。最后把code和脚本upload到服务器上，执行一下./run_lpsolve.sh，然后就可以安心去刷剧摸鱼等结果啦。03 Computational Results由于lpsolve只能使用单线程模式，因此在实验中也限制了CPLEX也只能使用单线程。关于表格一些列的说明：variable: 模型中变量的个数。constraint: 模型中约束的个数。non_zero: 约束Ax=b中，矩阵A中非0元素的个数。objective: 问题的目标值。time: 求解所花的时间。3.1 Netlib一共有96个算例，其中有5个CPLEX读取错误（我也不知道为啥。。），剩下91个算例中（平均variable=2524，平均constraint=978，平均non_zero=14763）：cplex能全部解到最优，平均求解时间为0.48s（yyds？）。lpsolve只求得了88个算例的最优解，这87个的平均求解的时间为0.89s。有三个算例在长时间内（大于2000s）无法得出可行解（表中标NA的单元格），手动终止了（用我导的话说，that's why lpsolve is free...）。clp比lpsolve更稳定一点，得出的所有结果和cplex一致，时间上也低于lpsolve。不同的地方在表格中已经加粗了。一些有趣的现象对于E226.SIF这个case，对比了几个solver，求解结果分别如下：官方报告的optimal: -18.7519cplex, gurobi, clp: -11.64matlab: -18.7519lpsolve: -25.86会不会是模型解析的问题呢？我把他们的模型打出来看过了，模型都是一样的，只是求解的结果不一样。至于为什么会这样，看到网上一个比较有趣的回答：MIP solvers work with floating-point data. For problems such as yours that have wide variations in the magnitude in the data, this leads to round-off errors. Any LP solver will have to perform operations on this data that can amplify the problem. In some cases like your problem, this can make the solver conclude that the problem is infeasible when it isn't. When you fix variables, the solver does fewer floating point operations.the commercial solvers solvers like Gurobi or cplex generally do a better job of working with numerically difficult data like yours. Gurobi has a parameter QuadPrecision that works with higher-precision floating point numbers. Most solvers have a parameter that will make the solver work better with numerically-difficult data. For example LPSolve has a parameter epsint that will make it relax what the it considers an integer. The default for the parameter is 10e-7, so 0.9999999 would be considered to be an integer, but 0.9999998 would not be. You can make this value larger, but you risk receiving unacceptable results.You are experiencing a leaky abstrction. Your problem is technically in the scope of Mixed-Integer Programming, but MIP solvers are not designed to solve it. Mixed Integer Programming is an NP-Hard problem. It is impossible to have a solver that works quickly and reliably on all inputs. MIP solvers try to work well on problems that come from diverse areas like portfolio optimization, supply chain planning, and network flows. They aren't designed to solve cryptology problems.出处：https://stackoverflow.com/questions/16001462/solving-an-integer-linear-program-why-are-solvers-claiming-a-solvable-instance3.2 L1数据集共34个cases，初步观察有以下的结论：lpsolve和clp差不多，cplex依然领先很多。有好几个cases，几个solver得出的解不一样，表中标粗的部分。最后经过测试发现，CPLEX中的pre_solve有可能会影响到最后的结果，按理说不应该影响才是，摘一点官网的介绍：Presolve consists in modifying the model to improve it so that it can be solved more efficiently.CP Optimizer presolves the input model before search. Presolve consists in modifying the model to improve it so that it can be solved more efficiently. Presolve works bysimplifying the model by reducing linear constraints by removing redundancies and fixed expressions andstrengthening the model to achieve more domain reduction by aggregating constraints or factorizing common subexpressions.As a consequence, the overall engine memory consumption can increase because an internal model is created to perform the improvement operations有可能是solver的一些bug。在lpsolve中也遇到过，用pre_solve以后居然直接说问题infeasible了？？？interesting。04 Conclusion这里有份开源的榜单，里面测了更多的solver，数据也更加权威，可以看到有很多国产的solver在榜单中都取得了很不错的成绩，希望国产的MILP也快快提上日程。http://plato.asu.edu/ftp/lpsimp.html总结一下，作为开源免费的LP solver， clp是一个不错的选择，目前cylp也还在逐渐开发。Google的or tools没有测因为他们的python接口还没有很完善。lp_solve比较出名了，但是感觉还是不太稳定吧，帮助文档倒是写得不错。
-
发表了文章 2022-04-23
机器学习在组合优化中的应用（上）
运筹学自二战诞生以来，现已被广泛应用于工业生产领域了，比如交通运输、供应链、能源、经济以及生产调度等。离散优化问题（discrete optimization problems）是运筹学中非常重要的一部分，他们通常可以建模成整数优化模型进行求解，即通过决定一系列受约束的整数或者0-1变量，得出模型最优解。有一些组合优化问题不是那么的“难”，比如最短路问题，可以在多项式的时间内进行求解。然而，对于一些NP-hard问题，就无法在多项式时间内求解了。简而言之，这类问题非常复杂，实际上现在的组合优化算法最多只能求解几百万个变量和约束的问题而已。机器学习是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。现在，有很多研究想将学习的方法应用与组合优化领域，提高传统优化算法的效率。By the way，大家请原谅我，有些单词我真不知道咋翻译，就直接用英文了，所以你们阅读的时候看见中英混用，绝不是我在装13，而是有些情景用英文大家理解起来会更方便。1 动机在组合优化算法中使用机器学习的方法，主要有两方面：（1）优化算法中某些模块计算非常消耗时间和资源，可以利用机器学习得出一个近似的值，从而加快算法的速度。（2）现存的一些优化方法效果并不是那么显著，希望通过学习的方法学习搜索最优策略过程中的一些经验，提高当前算法的效果。（算是一种新思路？）2 介绍这一节简要介绍下关于组合优化和机器学习的一些概念，当然，只是粗略的看一下，详细内容大家还是去参照以往公众号的文章（指的组合优化方面）。因为之前做的一直是运筹优化领域，对机器学习一知半解，所以关于这部分的阐述则是从网上筛选过来的，出处我均已贴到参考那里了。2.1 组合优化组合优化相信大家都很熟悉了，因为公众号一直在做的就是这方面的内容。一个组合优化问题呢通常都能被建模成一个带约束的最小化问题进行求解，即将问题以数学表达式的形式给出，通过约束变量的范围，让变量在可行域内作出决策，使得目标值最小的过程。如果决策变量是线性的，那么该问题可以称为线性规划（Linear programming）；如果决策变量是整数或者0-1，那么可以称为整数规划（Integer programming）；而如果决策变量是整数和线性混合的，那么可以称为混合整数规划（Mixed-integer programming）。可以利用branch and bound算法解决Mixed-integer programming问题，目前应用的比较多，也有很多成熟的求解器了，比如cplex、lpsolve、国产的solver等等。但是就目前而言，求解器在求解效率上仍存在着问题，难以投入到实际的工业应用中，现在业界用启发式比较多。2.2 监督学习(supervised learning)监督学习(supervised learning)的任务是学习一个模型，使模型能够对任意给定的输入，对其相应的输出做一个好的预测。监督学习其实就是根据已有的数据集，知道输入与输出的结果之间的关系，然后根据这种关系训练得到一个最优的模型。2.3 强化学习(Reinforcement learning)强化学习（Reinforcement Learning, RL），又称再励学习、评价学习或增强学习，是机器学习的范式和方法论之一，用于描述和解决智能体（agent）在与环境的交互过程中通过学习策略以达成回报最大化或实现特定目标的问题。[百度百科]马尔可夫决策过程（Markov Decision Processes,MDPs） MDPs 简单说就是一个智能体（Agent）采取行动（Action）从而改变自己的状态（State）获得奖励（Reward）与环境（Environment）发生交互的循环过程。MDP 的策略完全取决于当前状态（Only present matters），这也是它马尔可夫性质的体现。先行动起来，如果方向正确那么就继续前行，如果错了，子曰：过则勿惮改。吸取经验，好好改正，失败乃成功之母，从头再来就是。总之要行动，胡适先生说：怕什么真理无穷，进一寸有一寸的欢喜。即想要理解信息，获得输入到输出的映射，就需要从自身的以往经验中去不断学习来获取知识，从而不需要大量已标记的确定标签，只需要一个评价行为好坏的奖惩机制进行反馈，强化学习通过这样的反馈自己进行“学习”。（当前行为“好”以后就多往这个方向发展，如果“坏”就尽量避免这样的行为，即不是直接得到了标签，而是自己在实际中总结得到的）3 近来的研究第1节的时候，我们提到了在组合优化中使用机器学习的两种动机，那么现在很多研究也是围绕着这两方面进行展开的。首先说说动机（1），期望使用机器学习来快速得出一个近似值，从而减少优化算法中某些模块的计算负担，加快算法的速度。比如说在branch and price求解VRP类问题中，其子问题SPPRC的求解就是一个非常耗时的模块，如果利用机器学习，在column generation的每次迭代中能快速生成一些reduced cost为负的路径，那整个算法的速度就非常快了。不过这个难度应该会非常大，希望若干年后能实现吧~而动机（2）则是尝试一种新的思路来解决组合优化问题吧，让机器学习算法自己去学习策略，从而应用到算法中。比如branch and bound中关于branch node的选取，选择的策略能够极大地影响算法运行的时间，目前常见的有深度优先、广度优先等。但这些方法效果远没有那么出众，所以寄希望于新兴的机器学习方法，期望能得到一些新的，outstanding的策略。动机（1）和动机（2）下所使用的机器学习方法也是不同的，在开始介绍之前呢，大家先去回顾下第2节中介绍强化学习时提到的Markov链。假设environment是算法内部当前的状态，我们比较关心的是组合优化算法中某个使用了机器学习来做决策的函数，该函数在当前给定的所有信息中，返回一个将要被算法执行的action，我们暂且叫这样的一个函数为policy吧。那么这样的policy是怎样给出相应的action呢？所谓机器学习，当然是通过学习！而学习也有很多方式，比如有些人不喜欢听老师口口相传，只喜欢不听地做题，上课也在不停的刷题刷题（小编我）。有些人就上课认认真真听课，课后重点复习老师讲的内容。所有的方式，目的都是为了获得知识，考试考高分。同样的，在两种动机下，policy学习的方式也是不一样的，我们且称之为learning setting吧。动机（1）下使用的是demonstration setting，他是一种模仿学习，蹒跚学步大家听过吧~这种策略呢就是不断模仿expert做的决策进行学习，也没有什么reward啥的，反正你怎么做我也怎么做。他是通过一系列的“样例”进行学习，比如你把TSP问题的输入和最优解打包丢给他，让他进行学习，当他学有所成时，你随便输入一个TSP的数据，他马上（注意是非常快速的）就能给出一个结果。这个结果有可能是最优的，也有可能是近似最优的。当然，下面会举更详细的例子进行介绍。如下图所示，在demonstration setting下，学习的目标是尽可能使得policy的action和expert相近。动机（2）意在发现新的策略，policy是使用reinforcement learning通过experience进行学习的。他是通过一种action-reward的方式，训练policy，使得它不断向最优的方向改进。当然了，这里为了获得最大的reward，除了使用reinforcement learning algorithms的方法，也可以使用一些经典的optimization methods，比如genetic algorithms, direct/local search。简单总结一下，动机（1）中的模仿学习，其实是采用expert提供的一些target进行学习（没有reward）。而动机（2）中的经验学习，是采用reinforcement learning从reward中不断修正自己（没有expert）。在动机（1）中，agent is taught what to do。而在动机（2）中，agent is encouraged to quickly accumulate rewards。3.1 demonstration setting这一节介绍下目前使用demonstration setting的一些研究现状。（挑几个有代表性的讲讲，详情大家去看paper吧~）我们知道，在求解线性规划时，通过添加cutting plane可以tighten当前的relaxation，从而获得一个更好的lower bound，暂且将加入cutting plane后lower bound相比原来提升的部分称之为improvement吧。Baltean-Lugojan et al. (2018) 使用了一个neural network去对求解过程中的improvement进行了一个近似。具体做法大家直接去看文献吧，毕竟有点专业。第二个例子，就是我们之前说过的，使用branch and bound求解mixed integer programming的时候，如果选择分支的节点，非常重要。一个有效的策略，能够大大减少分支树的size，从而节省大量的计算时间。目前表现比较好的一个heuristic策略是strong branching (Applegate, Bixby, Chvátal, & Cook, 2007)，该策略计算众多候选节点的linear relaxation，以获得一个potential lower bound improvement，最终选择improvement最大那个节点进行分支。尽管如此，分支的节点数目还是太大了。因此，Marcos Alvarez, Louveaux, and Wehenkel (2014, 2017)使用了一个经典的监督学习模型去近似strong branching的决策。He, Daume III, and Eisner (2014)学习了这样的一个策略--选择包含有最优解的分支节点进行分支，该算法是通过整个分支过程不断收集expert的behaviors来进行学习的。3.2 experience开局先谈谈大家非常熟悉的TSP问题，在TSP问题中，获得一个可行解是非常容易的一件事，我们只需要依次从未插入的节点中选择一个节点并将其插入到解中，当所有节点都插入到解中时，就可以得到一个可行解。在贪心算法中，每次选择一个距离上次插入节点最近的节点，当然我们最直接的做法也是这样的。但是这样的效果，并没有那么的好，特别是在大规模的问题中。具体可以参考下面这篇推文：Khalil, Dai, Zhang, Dilkina, and Song (2017a)构建了一个贪心的启发式框架，其中节点的选择用的是graph neural network，一种能通过message passing从而处理任意有限大小graphs的neural network。对于每个节点的选择，首先将问题的网络图，以及一些参数（指明哪些点以及被Visited了）输入到neural network中，然后获得每个节点的action value，使用reinforcement learning对这些action value进行学习，reward的使用的是当前解的一个路径长度。结尾今天先介绍这么多了。以上内容都是小编阅读论文Machine learning for combinatorial optimization: A methodological tour d’horizon所得的，基本上翻译+自己理解。但是这个paper还没讲完哦，后面还有些许的内容，容我下篇推文再介绍啦。急不可耐的小伙伴可以直接去看原paper哦。参考监督学习(supervised learning)的介绍 https://zhuanlan.zhihu.com/p/99022922强化学习（Reinforcement Learning）知识整理 https://zhuanlan.zhihu.com/p/25319023强化学习（Q-Learning，Sarsa） https://blog.csdn.net/qq_39388410/article/details/88795124Baltean-Lugojan, R., Misener, R., Bonami, P., & Tramontani, A. (2018). Strong Sparse Cut Selection via Trained Neural Nets for Quadratic Semidefinite Outer-Approx- imations. Technical Report. Imperial College, London.Applegate, D., Bixby, R., Chvátal, V., & Cook, W. (2007). The Traveling Salesman Prob- lem: A Computational Study. Princeton University Press.Marcos Alvarez, A., Louveaux, Q., & Wehenkel, L. (2014). A supervised machine learning approach to variable branching in branch-and-bound. Technical Report. Université de Liège.Marcos Alvarez, A., Louveaux, Q., & Wehenkel, L. (2017). A machine learning-based approximation of strong branching. INFORMS journal on computing, 29(1), 185–195.He, H., Daume III, H., & Eisner, J. M. (2014). Learning to search in branch and bound algorithms. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, & K. Q. Weinberger (Eds.), Advances in neural information processing systems 27(pp. 3293–3301). Curran Associates, Inc.Khalil, E., Dai, H., Zhang, Y., Dilkina, B., & Song, L. (2017a). Learning combinatorial optimization algorithms over graphs. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 30 (pp. 6348–6358). Curran Associates, Inc..
-
发表了文章 2022-04-23
手把手教你用CPLEX求解一个数学模型（Java版）
一、前言小编有个小伙伴，隔三差五就过来跟我说：这个模型CPLEX怎么写呢？我说我不是给你讲过好多次？他说CPLEX太复杂了，俺没学过学不会呢。其实对于很多刚入行的小伙伴来说，CPLEX算不上友好，就连学习资料都不知道去哪里看，不像Excel或者Word，百度一下出来好多资料。其实吧，这玩意儿并没有大家想的那么难，尤其是简单使用CPLEX求解一个模型的话，用来用去都是那几个函数而已。下面小编来给大家好好理一下，看完相信你也能用CPLEX跑一下论文上的模型啦。当然啦，为了方便小编还是选择大家熟悉的Java平台，用Python也是可以的，处理数据可能还更方便。但是我们一般都是用Java写的算法，因此就统一平台啦。我们今天以一个最经典的VRPTW arc-flow model为例，手把手给大家演示下，CPLEX其实并不是那么的难用。二、模型集合定义运行一个模型之前，首先要定义模型中用到的一些参数和集合，如果这些都没有，是无从谈起的。因此没有的话第一步是要先生成这些数据哦。2.1 读取数据首先，你需要在程序中定义相关的变量（通常的做法是写一个instance的类，把算例的数据读进来，放到成员变量上。）比如：至于你怎么定义怎么写都无所谓啦，反正你知道这些数据对应模型的哪些参数就可以啦。2.2 定义集合其实小编发现，大家之所以觉得写模型难，还有一个原因就是自己建模的时候纯粹瞎搞。很多集合啊，参数啊，范围啊都没有想清楚，到写代码的时候就各种凌乱了。。。好了回到我们的正题，刚刚读入了算例。接下来我们需要定义模型中需要用到的集合，这些集合是哪些集合呢？就是我指出来的这些：然后你需要在程序中把这些集合给定义好了，然后把相应的数据填充进去，比如为所有节点的集合，为所有车辆集合，那么就for一下填充就好啦：for(i = 0; i < inst.nbCust + 2; ++i){ this.N.add(i); } for(i = 0; i < inst.nbVeh; ++i){ this.K.add(i); }当然了，在程序中不用定义这些集合也能实现我们的模型，这样做只是为了让程序更清晰，不至于到后面杂乱无章，debug起来也无从下手。三、CPLEX建模做完数据的定义，基本上就成功50%了。就像追女孩纸一样，当你喜欢她的时候就成功了50%，当她再喜欢你的时候，就100%成功了。现在我们就来完成剩下的50%。在CPLEX中，你只需要知道以下三点，就能轻松驾驭一个数学模型啦：决策变量定义添加优化目标添加约束想想也是哦，一个数学模型无非就是由决策变量、优化目标和约束组成嘛。下面我们来一个一个讲解。不过，在此之前，我们先new一个CPLEX的对象出来，并设置一些参数：this.cplex = new IloCplex(); this.cplex.setParam(IloCplex.Param.Simplex.Tolerances.Optimality, 1e-9); this.cplex.setParam(IloCplex.Param.MIP.Tolerances.MIPGap, 1e-9); this.cplex.setParam(IloCplex.DoubleParam.TimeLimit, 3600); this.cplex.setOut(null);第一第二句是求解精度相关的设置。倒数第二句表示设置求解时间为3600s，比较常用。最后一句是告诉CPLEX不要输出那些乱七八糟的东西，太烦啦！3.1 决策变量的定义首先是模型中有哪些变量，通通得定义出来。在CPLEX的Java API中，一个决策变量是一个对象来的，首先我们需要定义决策变量的数组，并分配数组的空间，比如的：this.x = new IloNumVar[n+1][n+1][v];IloNumVar这个表示它是一个num也就是数值类型的变量，就是可以为浮点数也可以为整数。这里我们只分配了数组空间，接下来 还需要为里面的每个引用分配一个对象（分配了房子，再给它发媳妇！）：//分配内存 //x 0-1变量 [n+1][n+1][v]; for(int i = 0; i < n+1; ++i){ for(int j = 0; j < n+1; ++j){ for(int k = 0; k < v; ++k){ x[i][j][k] = cplex.numVar(0, 1, IloNumVarType.Int, "x["+i+"]["+j+"]["+k+"]"); } } }其中cplex.numVar()这个函数呢就为我们new了一个数值变量的对象出来，我这里贴上官方的解释好啦：如果你有不同类型的变量，指定下第三个参数IloNumVarType就好啦：模型中另一个决策变量类似，我就不写啦。3.2 CPLEX的表达式首先来看一个概念：表达式是什么呢？呐，类似于我圈出来的这些：开始的时候，一般需要new一条IloNumExpr类型的空表达式出来，然后慢慢去填充它：IloNumExpr expr = this.cplex.numExpr();创建空表达式可以通过numExpr()函数哦：在CPLEX的JavaAPI中呢，涉及到CPLEX对象的一些表达式，是不能直接通过Java自带的+-*/进行运算的。需要通过CPLEX提供sum()、diff()、prod()函数进行加、减、乘的操作。那为什么没有除呢？因为除是可以通过转换变成乘的！比如可以转换成，没毛病吧~其中，sum()、diff()、prod()这些函数在CPLEX的库中重载了很多版本，也就是说你sum(IloNumExpr, double)、sum(IloNumExpr, IloNumExpr)、sum(double, IloNumExpr)都是可以识别的，那么我就贴一个出来给大家看看就好啦：sum()、diff()也是类似的，不过需要注意的是diff()时要注意区分是谁减去谁哦。现在表达式有了，我们来看看怎样通过sum()、diff()、prod()这些函数，实现模型中的式子。以目标那个式子为例：有三个求和符号，那么肯定得来三个循环啦：IloNumExpr objExpr = this.cplex.numExpr(); for(k : this.K){ for(i : this.N){ for(j : this.N){ IloNumExpr subExpr = this.cplex.prod(c[i][j], this.x[i][j][k]); obj = this.cplex.sum(obj, subExpr); } } }可能这一句obj = this.cplex.sum(obj, subExpr);大家有点晕，其实很简单，就是obj和subExpr相加，得到一个新的表达式，再赋值给obj。那么这样就能实现累加的效果了，大部分的求和表达式都可以写成这种形式哦。3.3 添加目标和约束好了，知道了表达式，添加目标和约束就变得非常简单啦。首先是目标的添加，CPLEX中提供了两个函数：addMinimize()和addMaximize()分别用以添加最小化目标和最大化目标。根据自己的需要调用就好，当然这两个函数也是有很多重载的版本，我就放一个最常用的给大家看看吧：参数就是一个IloNumExpr类型的表达式，比如可以直接把上面的objExpr给add进来，是不是很简单呢！对于添加约束，CPLEX也提供了三个函数，我这里写成一个表格方便大家查看：method作用addGe(a, b)添加约束addLe(a, b)添加约束addEq(a, b)添加约束根据a，b类型的不同，这几个函数同样重载了很多版本，你写addGe(IloNumExpr, double)、addGe(IloNumExpr, IloNumExpr)、addGe(double, IloNumExpr)都是可以的。我放一个官方的介绍吧：现在，我们来看看一个example，演示下如何添加约束（3.5）：首先，从哪着手呢？从右边开始：对于任意的，任意的，都要满足左边那个等式。两个循环是没跑了，然后在循环的最内层，把相关表达式给addEq就好了：for(h : this.C){ for(k : this.V){ //这里要开始写表达式啦 IloNumExpr subExpr1 = this.cplex.numExpr(); IloNumExpr subExpr2 = this.cplex.numExpr(); for(i : this.N){ subExpr1 = this.cplex.sum(subExpr1, this.x[i][h][k]); subExpr2 = this.cplex.sum(subExpr1, this.x[h][j][k]); } cplex.addEq(subExpr1, subExpr2); } }怎样，是不是很简单呢？当然了，这个easy是建立在一个清晰明了的模型基础之上的，如果你一开始的模型就设置得乱七八糟，这个过程写起来是很痛苦的。毕竟你要边写代码边修正模型，很可能写着写着就变成了一坨。。。四、CPLEX求解上面的模型建立完成以后，就可以调用solve()函数进行求解了，如果返回true，那么就找到了可行解（是的吧？我也不太清楚，可以去查查）。否则就是不可行解。求解完成以后，获取一个变量的值可以采用CPLEX的getValue()函数，参数是你new出来的决策变量。不过求解得到结果以后，是需要最好手动或者写个函数验算下，确保得到的解满足了所有约束。以及得到的目标值也是正确的。总的来说，CPLEX已经为我们封装好了很多东西，大部分只需要动动手指就可以直接使用了。少部分可能需要查查库什么的，但是基本的时候已经非常简单了。最后，贴上两篇文章，大家可能会比较感兴趣，小编也建议大家结合起来看，效果会更好哦：CPLEX出现'q1' is not convex？干货|十分钟快速掌握CPLEX求解VRPTW数学模型（附JAVA代码及CPLEX安装流程）快点个赞关注我们。获取更多精彩内容吧~大家帮忙点个在看，让更多小伙伴知道吧~
-
发表了文章 2022-04-23
10分钟教你用Python爬取Baidu文库全格式内容
这个学期上了Python课，最后的结课方式是大作业的形式，这可把小编乐坏了。考虑到现在大部分小伙伴使用Python主要因为爬虫，那么为了更好地帮助大家巩固爬虫知识，加深对爬虫的理解，我们小组选择了爬取百度文库作为我们的大作业。现在将我们的大作业分享出来，希望能够帮助到大家。本文目录包含以下内容：TXT,DOCX爬取与保存（文本格式）PPT,PDF爬取与保存（图片格式）简单的GUI制作 通过本文你将收获：基本的爬虫技能DOCX,Image库的使用废话不多说，我们开始。TXT,DOCX爬取与保存在爬取任何东西之前，我们都要先确认需要爬取的数据是不是异步加载的。如果是异步加载的直接爬取网页是爬不到的。要知道是不是异步加载其实很简单，就用request对网页发起请求，看看response是什么就可以了。url = 'https://wenku.baidu.com/view/4e29e5a730126edb6f1aff00bed5b9f3f90f72e7.html?rec_flag=default' header = {'User-agent': 'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/81.0.4044.138 Safari/537.36'} res = requests.get(url , headers = header) res.text很明显，返回的东西，并不是我们所需要的内容。根据常理来说，我们就可以认为该网页是异步加载的。但是，从常识来讲，如果网页的内容是异步加载的，那么直接通过百度搜索，是搜索不到网页内部的内容的，但是很显然，我们每次通过百度搜索都是可以直接找到文库中的文本内容的。如下:那么这就有意思了，明明直接发起请求是获取不到网页内容的，但是为什么通过百度搜索就可以找到呢？关键肯定在于百度搜索上面。这个时候通过查阅资料，我们了解到，最主要的问题出在我们的headers。在爬取网页时，headers通常是作为身份证，让网页不看出我们是爬虫。如果不加headers，网页直接就会看出我们是爬虫，就会拒绝访问。再深入了解以下headers的识别机理，我们发现了叫做Robot协议的东西。它规定了什么样的headers可以访问网页内部内容，除了指定headers之外的headers，都是无法请求页面内容的。（更详细的Robot协议介绍以附件形式给出）比如说百度文库的Robot协议就是下面这样的。User-agent: Baiduspider Disallow: /w? Disallow: /search? Disallow: /submit Disallow: /upload Disallow: /cashier/而我们需要爬取的内容url格式为https://wenku.baidu.com/view/?.html这代表Baiduspider应该可以爬取文库内容。大致猜测这是因为百度搜索时需要根据文本内容匹配搜索选项，所以放行。因此我们尝试伪装User-agent为Baiduspider。url = 'https://wenku.baidu.com/view/4e29e5a730126edb6f1aff00bed5b9f3f90f72e7.html?rec_flag=default' header = {'User-agent': 'Googlebot'} res = requests.get(url , headers = header) res.text果然不出所料，我们成功地获取到了目标内容。既然已经成功获取到了网页的正确源代码，那么下一步就是去解析网页获取内容。解析网页源代码的库有很多，这里我们使用BeautifulSoup。plist = [] soup = BeautifulSoup(r, "html.parser") plist.append(soup.title.string) for div in soup.find_all('div', attrs={"class": "bd doc-reader"}): plist.extend(div.get_text().split('\n')) plist = [c.replace(' ', '') for c in plist] plist = [c.replace('\x0c', '') for c in plist] plist整个解析是非常容易的，都是很标准的操作。在这里就不多加叙述了。最终的效果如下。当然爬取到东西了只是万里长征的第一步，就这样是肯定不行的，我们还需要将爬取的内容保存起来，通常是保存为txt文件。file = open('test.txt', 'w',encoding='utf-8') for str in plist: file.write(str) file.write('\n') file.close()但是为了美观起见，我们在这里选择使用python-docx库将内容保存为docx文件。with open('test.txt', encoding='utf-8') as f: docu = Document() docu.add_paragraph(f.read()) docu.save('test.docx')PPT,PDF爬取与保存有了之前的经验教训，在爬取的时候我们首先就尝试了使用爬取TXT,DOCX的方法，尝试是否可以爬到内容。url = 'https://wenku.baidu.com/view/a4ac1b57dd88d0d232d46a0f.html?fr=search' header = {'User-agent': 'Googlebot'} res = requests.get(url , headers = header) res.text很可惜的是，我们并没有访问到。原因仔细想想也很简单，在百度搜索的时候，直接搜索是搜不到PPT或者PDF的内容的。那么很显然，PPT和PDF是通过异步的方法进行内容加载的。对待异步加载的数据，我们通常采取的策略有两种，第一个就是直接找到发起异步请求的接口，自己构造请求头，发起请求，第二个就是通过Selenium这样的自动化测试工具去爬取。百度文库的接口太难找了，请求头的构造也很麻烦，找了很久也没有很满意。所以在本次爬取中，我们使用的是第二种方法，使用Selenium这样的自动化测试工具。在这里不多加介绍WebDriver，有兴趣的小伙伴可以自己查一下，我们直接上手使用。这里我们需要下载ChromeDriver这个插件，当然这里是默认大家使用的是Chrome浏览器，如果是其他的浏览器，firefox，safari等等，直接去网上找到相应Driver就可以了。这里给出ChromeDriver的下载地址：http://npm.taobao.org/mirrors/chromedriver/大家一定要下载和自己Chrome浏览器版本一致的ChromeDriver，不然程序是运行不起来的。我们先不急着马上开始爬取，我们先来尝试使用一下Selenium调用ChromeDriver。import requests from selenium import webdriver url = 'https://wenku.baidu.com/view/5292b2bc0166f5335a8102d276a20029bd64638c.html?fr=search' driver = webdriver.Chrome(r'F:\driver\chromedriver.exe') driver.get(url)怎么样，是不是浏览器自动打开了?现在我们尝试输出这个driver，就可以看见，网页的正确源代码已经在里面了。现在我们仔细研究一下源代码就可以看到，我们需要的内容在下面这个位置。现在正确的源代码也有了，内容的位置也知道了，直接解析，爬取，完事就好了。想得美，经过这样的爬取之后，对内容进行解析，让我们看看究竟爬到没有。from lxml import etree import re html=etree.HTML(driver.page_source) links=html.xpath("//div[@class='reader-pic-item']/@style") part = re.compile(r'url[(](.*?)[)]') qa="".join(links) z=part.findall(qa) z我们可以知道，其实我们只爬到3张PDF，其他的都没有爬到。这是为什么呢？这是百度文库为了防止大家去爬，专门设置的一个小机关。返回百度文库，我们仔细看看源代码，其实我们可以发现，随着页面的变化，源代码是不断改变的，每次都只有3张图片的url。并且这个页码数也有一定的规律，如果在第二页，那么图片就是1，2，3，如果在第三页，图片就是2，3，4。那么我们的疑惑一下就解决了，只需要不断地进行换页的爬取，就可以了。接下来就是如何实现换页的操作了。这个需要两个步骤，先是点击继续阅读，然后进行页面输入实现换页。先实现点击的操作，代码如下。button = driver.find_element_by_xpath("//*[@id='html-reader-go-more']/div[2]/div[1]/span") button.click() driver.execute_script("arguments[0].click();", button)整个操作是通过JS来进行的，大家可以把这个记住，以后需要点击的时候直接用就可以。然后就是输入页面实现换页，这个其实涉及的比较多，细分的话，步骤分为获取总页数，依次输入页面并点击。import re # 寻找页面 source = re.compile(r'<span class="page-count">/(.*?)</span>') number = int(source.findall(driver.page_source)[0]) # 输入页面并点击 driver.find_element_by_class_name("page-input").clear() driver.find_element_by_class_name("page-input").send_keys('2') driver.find_element_by_class_name("page-input").send_keys(Keys.ENTER)如果小伙伴成功实现了上面的操作，其实大体的爬取工作已经差不多了，接下来就是保存我们的PPT和PDF了。因为爬取PDF和PPT的时候，我们是爬取的图片的源地址，那么我们要获得这张图片并保存下来就必须对这个地址发起请求，然后将返回头以二进制保存下来。for m in range(3): pic = requests.get(z[m]).content # 方法一 # file = open(f'./照片/{m+1}.jpg','wb') # file.write(pic) # file.close() # 方法二 with open(f'./照片/{m+1}.jpg','wb') as f: f.write(pic) f.close()在这里，提醒大家一下一定要按照对图片用正确顺序进行命名，因为后面保存为PDF的时候，需要排序。在py文件的目录下，大家就可以看见保存下来的图片了。最后一步，将图片保存为PDF。from PIL import Image import os folderPath = "F:/TEST" filename = "test" files = os.listdir(folderPath) jpgFiles = [] sources = [] for file in files: if 'jpg' in file: jpgFiles.append(file) tep = [] for i in jpgFiles: ex = i.split('.') tep.append(int(ex[0])) tep.sort() jpgFiles=[folderPath +'/'+ str(i) + '.jpg' for i in tep] output = Image.open(jpgFiles[0]) jpgFiles.pop(0) for file in jpgFiles: img = Image.open(file) img = img.convert("P") sources.append(img) output.save(f"./{filename}.pdf","PDF",save_all=True,append_images=sources)最终的结果就是生成了咱们的PDF文件。上述的操作看起来很多，很麻烦，其实并不是的。因为大部分的操作都是固定的，大家只需要记熟就可以了。简单的GUI制作GUI这块，我们整了点新活儿，用C#编写winform简易的GUI，调用爬虫的python代码。C#调用python项目的方式我简单用Process类执行，通过执行python.exe执行代码。public static void RunPythonScript(string sArgName, string py, string args = "", params string[] teps) { Process p = new Process(); //(没放debug下，写绝对路径) //string path = @"C:\Users\zll\Desktop\baidu\CSharpCallPython\bin\Debug\" + sArgName; // 获得python文件的绝对路径（将文件放在c#的debug文件夹中可以这样操作） string path = System.AppDomain.CurrentDomain.SetupInformation.ApplicationBase + sArgName; //没有配环境变量的话，可以像我这样写python.exe的绝对路径。如果配了，直接写"python.exe"即可 //p.StartInfo.FileName = @"C:\Users\zll\AppData\Local\Programs\Python\Python37-32\python.exe"; p.StartInfo.FileName = @py; string sArguments = path; foreach (string sigstr in teps) { sArguments += " " + sigstr;//传递参数 } sArguments += " " + args; p.StartInfo.Arguments = sArguments; p.StartInfo.UseShellExecute = false; p.StartInfo.RedirectStandardOutput = true; p.StartInfo.RedirectStandardInput = true; p.StartInfo.RedirectStandardError = true; p.StartInfo.CreateNoWindow = true; p.Start(); p.BeginOutputReadLine(); p.OutputDataReceived += new DataReceivedEventHandler(p_OutputDataReceived); Console.ReadLine(); p.WaitForExit(); }对输入的内容进行简单判断，如果不是百度文库地址或不是python.exe地址，报错。if (!url.Contains("https://wenku.baidu.com/view/")) { MessageBox.Show("请输入正确的百度文库网址！"); lbl_state.Text = "请重新输入。"; } else if (!py.Contains("python.exe")) { MessageBox.Show("请输入正确的python.exe路径！"); lbl_state.Text = "请重新输入。"; } else { //输入参数列表 String[] strArr = new String[] { url, istxt }; string sArguments = @"src\wenku.py";//这里是python的文件名字 RunPythonScript(sArguments, py, "-u", strArr); if(result.Contains("0")) lbl_state.Text = "对不起，爬取失败。"; else if (result.Contains("1")) lbl_state.Text = "爬取成功！"; }因为GUI部分比较简单，学过C#的同学应该都看的明白（没学过的呢？），这里就不多讲解了。
-
发表了文章 2022-04-23
使用Picgo+GitHub+ jsDelivr搭建CDN加速免费图床
前言经常写Markdown或者博客的同学，肯定都要用到图床。图床是什么呢？其实相当于一个存储图片的网站，类似百度云这样，不过上传图片到图床后可以直接通过外链进行访问。比如把本地一张a.jpg上传到图床后，便可以拿到一个链接：https://www.xxx.com/img/a.jpg然后点击这个链接就可以访问图片a了。今天来聊聊怎么搭建可靠的图床吧~为什么会产生这个需求呢？因为小编经常写博文什么的，现在的做法是在简书上上传图片，然后把生成的图片链接放到Markdown文档上面，写好文档以后就可以批量复制到各大博客平台投稿了。但是这样有个隐患：万一简书哪天挂掉了，那么我放到csdn、cnbolgs等这些平台的文章图片都会挂掉。即使简书一直维持现状，但万一哪天它不高兴了，做了个外链防盗（图片外链只能在本站显示），那同样会遇到上面的问题。比如小编之前放在简书上的文章，复制到csdn上后。不知道怎么回事：说多了都是泪。因此，趁早做好准备，免得以后出现问题就麻烦了。毕竟有些博客的图片只是随手一截，还真找不到备份……前期准备平台选择现在也有蛮多的图床平台可以选择，常见的有SM.MS图床、腾讯云COS、微博图床、GitHub图床、七牛图床、Imgur图床、阿里云OSS、又拍云图床等。而这里边，SM.MS和Imgur有免费版也有收费版，腾讯云、七牛、阿里云、又拍云都是收费的，微博图床据说已经挂了。其他小站的就不推荐了，因为指不定哪天就挂了。那么，也就剩下GitHub安全、免费又可靠了（微软爸爸护着呢！）。现在微软接管了GitHub以后，貌似公有仓库已经不限个数了，而且单个仓库容量已经放宽至2GB。这绝对够用了，不够就再建一个共有仓呗。最重要的还是免费，配合CDN加速，访问也不成问题。嗯，就微软爸爸了！工具选择选择一个本地的上传工具是为了方便我们快速上传图片，获得图片外链。这里首选picgo。介绍和下载地址：https://github.com/Molunerfinn/PicGo这款小工具非常强大，其中最赞的就是那个剪切板图片上传功能，在QQ或者微信截图截好图片后，可以点击剪切板图片上传或者通过快捷键，它就会把当前剪切板中的图片上传到配置到图床中。可以看到上传所有图片，点击即可复制需要的图片外链格式：配置准备完毕就可以着手配置了。先去GitHub，没有账号的先注册一个账号。GitHub配置1. 创建Repository鼠标移动到右上角，点击"New repository"按钮：填写相关信息，创建一个存储图片的仓库：2. 配置token key生成一个Token用于操作GitHub repository。回到主页，点击"Settings"按钮：进入页面后，点击"Developer settings"按钮点击"Personal access tokens"按钮，然后点击Generate token：填写描述，选择"repo"权限，然后拉到下面点击"Generate token"按钮注意：创建成功后，会生成一串token，这串token之后不会再显示，所以第一次看到的时候，可以用个小本本保存起来哦，忘记了只有重新生成，每次都不一样。Picgo配置拿到了刚刚记录了GitHub token后，打开picgo，按照如下设置即可：设定仓库名按照“账户名/仓库名的格式填写”，比如我的是：dengfaheng/image01。分支名统一填写“master”。设定Token将之前的Token粘贴在这里。指定存储路径留空。自定义域名的作用是在上传图片后成功后，PicGo会将“自定义域名+上传的图片名”生成的访问链接，放到剪切板上。默认留空也可以正常使用。这里为了使用CDN加快图片的访问速度，自定义域名我们按照这样去填写：https://cdn.jsdelivr.net/gh/GitHub用户名/仓库名比如我的是：https://cdn.jsdelivr.net/gh/dengfaheng/image01点击确定后就配置完成了，我们截图后点击剪切板图片上传，如果上传成功，拿到的外链放到Markdown中正常访问，就OK啦。当然快捷上传的快捷键也可以到设置中进行配置。可以看到GitHub仓库中多了很多我们上传的图片。也可以在picgo中对上传的图片进行相关操作，不过这里的删除只是删除picgo中的图片而言，GitHub上的不会删除哦。至于如何删除GitHub上的图片，emmm……那说来就话长了。。就不说了。大家还是不要删了，空间不够了再开个仓库即可。
-
发表了文章 2022-04-23
令人头疼的代码命名规范……
前言关于代码命名，我相信是经常困扰很多小伙伴的一个问题，尤其是对于强迫症晚期患者。怎么说呢，每次小编在写代码之前，总会在想啊想啊，用什么命名法好呢？对于经常在C++、Java、Python等主流语言上切换的强迫症来说，换个语言换种命名风格简直不要太混乱。今天就来梳理一下常见的代码命名规范以及适用范围吧。常见命名规范为什么需要命名规范呢？世界级软件大师 Martin Fowler 大神都说过 CS 领域有两大最难的事情，一是缓存失效，一是程序命名。《Clean Code》这本书明确指出：代码的注释不是越详细越好。实际上好的代码本身就是注释，我们要尽量规范和美化自己的代码来减少不必要的注释。若编程语言足够有表达力，就不需要注释，尽量通过代码来阐述。要想让你的编程语言足够有表达力，良好的命名规范是必不可少的。同时，花几分钟学学规范的命名，也能让你的代码看起来赏心悦目，何乐而不为呢。1. 驼峰命名法（CamelCase）骆驼式命名法（Camel-Case）又称驼峰式命名法，是电脑程式编写时的一套命名规则（惯例）。正如它的名称CamelCase所表示的那样，是指混合使用大小写字母来构成变量和函数的名字。程序员们为了自己的代码能更容易的在同行之间交流，所以多采取统一的可读性比较好的命名方式。它又可以分为以下几种。小驼峰命名法（lowerCamelCase）除第一个单词之外，其他单词首字母大写。方法名、参数名、成员变量、局部变量需要使用小驼峰命名法（lowerCamelCase）。比如：getUserInfo() createCustomThreadPool() findAllByUserName(String userName) TaskRepository taskRepository;大驼峰命名法（CamelCase）相比小驼峰法，大驼峰法（即帕斯卡命名法）把第一个单词的首字母也大写了。常用于类名，命名空间等。如：class TaskDateToSend{} class TaskLabelToSend{} SettingRepository2. 蛇形命名法（snake_case）蛇形法是全由小写字母和下划线组成，在两个单词之间用下滑线连接即可。测试方法名、常量、枚举名称需要使用蛇形命名法（snake_case）。如：first_name last_name MAX_ITERATION LAST_DATA3. 串式命名法（kebab-case）在串式命名法中，各个单词之间通过下划线“-”连接，比如：hello-world first-project建议项目文件夹名称使用串式命名法（kebab-case），比如 dubbo 项目的各个模块的命名是下面这样的：总结一下语言场景给出各个场景下的命名规则，大家要养成习惯。事实上，如果经常在各个语言上切换的话，真的可能搞混。所以今天就Mark一下吧。Java命名规范总体命名规范类名需要使用大驼峰命名法（UpperCamelCase）风格。方法名、参数名、成员变量、局部变量需要使用小驼峰命名法（lowerCamelCase）。测试方法名、常量、枚举名称需要使用蛇形命名法（snake_case） ，比如test_get_user()、TIME_LIMIT。并且，测试方法名称要求全部小写，常量以及枚举名称需要全部大写。项目文件夹名称使用串式命名法（kebab-case），比如dubbo-registry。包名统一使用小写，尽量使用单个名词作为包名，各个单词通过 "." 分隔符连接，并且各个单词必须为单数。抽象类命名使用 Abstract 开头。如：public abstract class AbstractClient extends AbstractEndpoint{}。异常类命名使用 Exception 结尾。如：public class NoSuchMethodException extends RuntimeException{}。测试类命名以它要测试的类的名称开始，以 Test 结尾。如：public class AnnotationUtilsTest{}。包名命名规范Java的包名由小写单词组成，包的路径符合所开发的系统模块的定义，以便通过包名可得知其属于哪个模块，从而方便到对应包里找相应的实现类。常规包名为了保障每个Java Package命名的唯一性,在Java编程规范中要求开发人员在自己定义的包名前加上唯一的前缀.由于互联网上的域名称是不会重复的,所以多数开发人员采用自己公司在互联网上的域名称作为自己程序包的唯一前缀.例如 : com.sun.swt...公司项目 com : 公司项目,copyright由项目发起的公司所有. 包名 : com.公司名.项目名.模块名..团队项目 team : 团队项目,指由团队发起,并由该团队开发的项目,copyright属于该团队所有. 包名 : team.团队名.项目名.模块名..自定义包名一般公司命名为com.公司名.项目名.模块名....那我们个人的项目又怎么命名呢?个人的英语单词有individual、personal、private、one-man,进一步对以上四个单词词意进行分析并在保证了唯一性,继而使用每个单词的前4个字母作为前缀,与com也做了区分.示例如下所示:indi : 个体项目,指个人发起,但非自己独自完成的项目,可公开或私有项目,copyright主要属于发起者. 包名 :indi.发起者名.项目名.模块名..pers : 个人项目,指个人发起,独自完成,可分享的项目,copyright主要属于个人.包名 : pers.个人名.项目名.模块名..priv : 私有项目,指个人发起,独自完成,非公开的私人使用的项目,copyright属于个人.包名 : priv.个人名.项目名.模块名..onem : 与indi相同，推荐使用indi.Python命名规范类：总是使用首字母大写单词串。如MyClass、ClassName。内部类可以使用额外的前导下划线。函数和方法：小写+下划线，如method_name。函数参数：小写+下划线，如function_parameter_name。如果一个函数的参数名称和保留的关键字冲突，通常使用一个后缀下划线，如random_。全局变量：对于from M import *导入语句，如果想阻止导入模块内的全局变量可以使用旧有的规范，在全局变量上加一个前导的下划线，如_var_name。应避免使用全局变量。变量：小写，由下划线连接各个单词。如color、this_is_a_variable。注意：不论是类成员变量还是全局变量，均不使用 m 或 g 前缀。私有类成员使用单一下划线前缀标识。变量名不应带有类型信息，因为Python是动态类型语言。如 iValue、names_list、dict_obj 等都是不好的命名。常量：常量名所有字母大写，由下划线连接各个单词如MAX_OVERFLOW，TOTAL。异常：以“Error”作为后缀。文件名：全小写,可使用下划线包：应该是简短的、小写的名字。如果下划线可以改善可读性可以加入，如mypackage。模块：与包的规范同，如mymodule。缩写：命名应当尽量使用全拼写的单词，缩写的情况有如下两种：常用的缩写，如XML、ID等，在命名时也应只大写首字母，如XmlParser。命名中含有长单词，对某个单词进行缩写。这时应使用约定成俗的缩写方式。例如：function 缩写为 fn text 缩写为 txt object 缩写为 obj count 缩写为 cnt number 缩写为 num，等。前导后缀下划线：一个前导下划线：表示非公有。一个后缀下划线：避免关键字冲突。两个前导下划线：当命名一个类属性引起名称冲突时使用。两个前导和后缀下划线：“魔”（有特殊用图）对象或者属性，例如__init__或者__file__。绝对不要创造这样的名字，而只是使用它们。注意：关于下划线的使用存在一些争议。特定命名方式：主要是指 xxx 形式的系统保留字命名法。项目中也可以使用这种命名，它的意义在于这种形式的变量是只读的，这种形式的类成员函数尽量不要重载。如 class Base(object): def init(self, id, parent = None): self.id = id self.parent = parent def message(self, msgid): 其中 id、parent 和 message 都采用了系统保留字命名法。Python推荐使用蛇形命名法，因为 Python 是蟒蛇啊，理所当然是用蛇形命名……综合各方面考虑，驼峰式命名法比较好，优势明显，事实上，目前使用驼峰式命名法的人也真的越来越多了。最后，大家是在命名有困难可以上一个神奇的网站：https://unbug.github.io/codelf/reference三种编程命名规则：驼峰命名法 （壹）：https://www.jianshu.com/p/de0016754d8a因为命名被主管diss无数次。简单聊聊编程最头疼的事情之一：命名：https://www.toutiao.com/i6836703460176429582/Java 命名规范：https://www.cnblogs.com/wkfvawl/p/12172756.htmlPython 为什么推荐蛇形命名法？：https://www.cnblogs.com/pythonista/p/13155167.html
-
发表了文章 2022-04-23
10分钟教你用Python打造学生成绩管理系统
大家好，这学期上了Python这门课，然后结课的时候老师要求做一个这样的学生管理系统。自己按照老师的要求写了一下，今天就把这个小程序分享出来吧~供Python新手小朋友学习~1总体构思其实类似这类信息管理系统之类的程序，核心还是和数据打交道吧，包括增删查改，读取、展示、保存等。在数据结构上，我依然用了给定的数据结构，即：score1 = { "姓名":"张三丰", "学号":"U19990001", "作业" : [80, 64, 67, 20], "测验" : [75, 75], "实验" : [78, 57] , "分数" : 0 }没有增加新的字段比如排名之类的。这样做的主要是考虑到排名、平均成绩等均可以由上述结构中的信息计算出来，而且也可以避免因为一个某个成绩变动，导致一系列的数据需要重新计算。毕竟，数据存储得越多，维护起来的难度就越大，特别是一些关联密切的数据更是如此。在存储在结构上，我采用了Python中常用的列表作为此程序的“数据库”，因为列表操作起来还是非常方便的。此外，因为这里涉及到一个排名的问题，所以我制定了一个原则：在列表中的所有数据实体都是按照成绩高低进行排序的，即整个存储信息的列表由始至终都是有序的。这样就解决了排名的问题，至于如何实现的，后续我会进行阐述。运行环境采用的是Windows 10 x64位操作系统+anaconda（Python3.7）+Spyder，默认情况下即可运行，不需要安装其他库。2程序说明这一节将介绍一下该程序相应的功能以及相应的代码实现。在此之前先介绍设定的一些规则：> 计算成绩时取小数点后三位。> 排名根据[分数、作业平均、测验平均、实验平均]的优先级比较。不存在排名相同的情况。如果这4项指标都相同，emmm应该不会有这么巧的事情。> 文件保存和读取时，采取CSV格式的数据文件。文件头遵循['序号','姓名','学号','分数','排名','作业1','作业2','作业3','作业4', '测验1', '测验2', '实验1', '实验2']这种格式。2.0 主界面整个程序的主界面如下：在整个程序的交互中，为了更好提高提示信息的辨识度，系统规定了几种颜色：- 蓝色提示内容表示需要用户输入相关信息。- 红色表示系统执行指令的结果，比如成功，失败等等。- 黑色表示系统菜单显示啊，查询结果的输出等。2.1 添加学生信息在添加学生信息中，在实现了手动添加信息的基础上，我又增加了从文件中导入信息的功能。不过在添加信息这块，我做了一个约束：添加学生信息时，如果系统中已经存在该学生的学号，则不能重复添加。两种方式都遵循该原则，以保证学号的唯一性。在添加学生信息时，因为前面说了列表里面的数据需要保持有序性，所以采取了插入排序的方式进行添加，核心的代码如下：# 根据优先级[分数、作业平均、测验平均、实验平均]比较s1是否优于s2 def cmp_student(s1, s2): if s1["分数"] != s2["分数"]: return s1["分数"] > s2["分数"] else: if np.mean(s1["作业"]) != np.mean(s2["作业"]): return np.mean(s1["作业"]) > np.mean(s2["作业"]) else: if np.mean(s1["测验"]) != np.mean(s2["测验"]): return np.mean(s1["测验"]) > np.mean(s2["测验"]) else: return np.mean(s1["实验"]) > np.mean(s2["实验"]) # 根据分数大小，将学生信息插入到列表中，插入排序 def add_to_list(stu, stu_list): if len(stu_list): if cmp_student(stu, stu_list[0]): # 比第一名还优秀 stu_list.insert(0,stu) elif not cmp_student(stu, stu_list[-1]): # 比最后一名还差 stu_list.append(stu) else: for i in range(len(stu_list)-1): if (not cmp_student(stu, stu_list[i])) and (cmp_student(stu, stu_list[i+1])): stu_list.insert(i+1, stu) return else: stu_list.append(stu)原谅我写了这么多if！手动添加时，逐个输入学生的信息，最后按照分数插入到相应的位置，注意的是，需要保证在输入成绩时确保获取的是数字，否则提示错误需要用户重新输入：# 输入一个数字 def input_number(information): while True: try: print("\033[34m",end='') number = input(information) print("\033[0m",end='') if type(eval(number)) == float or type(eval(number)) == int: return float(number) except : print('\033[1;31m',end='') print("输入有误，请输入一个数字！") print('\033[0m',end='')注：类似print("\033[34m",end='')这类语句是控制输出的字体颜色的。下同从文件中添加时，系统提供了默认文件的选项，直接回车则默认从data_file目录下的学生成绩信息.csv文件导入，因为有些用户是懒得输入文件名的。需要注意的是，导入的文件中，允许成绩选项缺失，如果缺失了，则利用其它成绩重新计算得出。但其它必要信息不能缺失：# 从文件添加学生信息 # 需要遵循格式：['序号','姓名','学号','分数','排名','作业1','作业2','作业3','作业4', '测验1', '测验2', '实验1', '实验2'] def add_from_file(stu_list): print("\033[34m",end='') fn = input("请输入文件路径(例如: C:/a.csv, 直接回车则默认为[./data_file/学生成绩信息.csv]) >> ") print("\033[0m",end='') file_path = './data_file/'+'学生成绩信息.csv' # 默认选项 if fn != '': file_path = fn n = 0 n_du = 0 with open(file_path) as csvfile: csv_reader = csv.reader(csvfile) # 使用csv.reader读取csvfile中的文件 next(csv_reader) # 跳过文件头 for row in csv_reader: # 读取数据 if find_student_uid(row[2], stu_list) != -INF: # 如果存在学号相同，则不添加 n_du = n_du + 1 continue work = [float(x) for x in row[5:9]] #转化作业成绩 test = [float(x) for x in row[9:11]] #转化测验成绩 experiment = [float(x) for x in row[11:]] #转化实验成绩 score = 0 if row[3] == '': score = calc_score(work, test, experiment) # 考虑到成绩位置为空的情况，重新计算成绩。 else: score = float(row[3]) stu_info = {'姓名':row[1], '学号':row[2], '作业':work, '测验':test, '实验': experiment, '分数':score} add_to_list(stu_info,stu_list) #将字典数据添加到列表中，插入排序。 n = n + 1 print('\033[1;31m') print("从文件["+file_path+"]添加信息成功！共添加 "+str(n)+" 条信息，跳过 "+str(n_du)+" 条重复信息！") print('\033[0m') return stu_list2.2 修改学生信息这一块比较简单，找到学生信息后，输入相应信息然后修改。大部分都是提示输入的语句。不过需要注意的是，修改了相应的作业、实验等成绩后，需要更新学生的分数，同时重新计算学生的排名，将该生挪到列表的相应位置上。具体做法在我的代码实现中比较简单，先将该生从列表中移除，重新计算分数后再按照插入排序的思路放进列表即可。这样速度可能会快一些。因为变动信息的只有一个学生，如果再次对整个列表进行排序可能会造成比较大的开销。2.3 删除学生信息这一块也相对来说比较简单，找到学生后，如果确认删除，则直接删除该学生即可。删除后其他学生的次序依然是有序的，无需再做调整。2.4 查找学生信息查找学生相关信息是通过`学号`遍历列表进行搜寻，找到后输出学生的相关信息。不过我在此基础上，对学生成绩进行了简单的统计，并通过图表的方式进行呈现。能够让老师或学生更直观地看到各科成绩的详细内容，找出自己的优势与不足，便于下次努力改进。（不过这里因为想把两个图拼在一个图上，因为不熟悉操作做了好久^~^）bar1_colors = ['#7199cf','#4fc4aa','#e1a7a2'] labels = np.array(['作业1','作业2','作业3','作业4','测验1','测验2','实验1','实验2']) name=['作业','测验','实验'] # 统计学生成绩等信息 def statistics_student(stu): #=======自己设置开始============ #标签 #数据个数 dataLenth = len(stu["作业"])+len(stu["测验"])+len(stu["实验"]) #数据 all_scores = stu["作业"] + stu["测验"] + stu["实验"] data = np.array(all_scores) average_score=[np.mean(stu["作业"]),np.mean(stu["测验"]),np.mean(stu["实验"])] #========自己设置结束============ angles = np.linspace(0, 2*np.pi, dataLenth, endpoint=False) data = np.concatenate((data, [data[0]])) # 闭合 # #将数据结合起来 angles = np.concatenate((angles, [angles[0]])) # 闭合 fig = plt.figure(figsize=(8, 4.2), dpi=80) ax = fig.add_subplot(121, polar=True)# polar参数！！121代表总行数总列数位置 ax.plot(angles, data, 'bo-', linewidth=1)# 画线四个参数为x,y,标记和颜色，闲的宽度 ax.fill(angles, data, facecolor='r', alpha=0.1)# 填充颜色和透明度 ax.set_thetagrids(angles * 180/np.pi, labels, fontproperties='SimHei') ax.set_title("{} 详细成绩雷达图".format(stu["姓名"]),fontproperties='SimHei',weight='bold', size='medium', position=(0.5, 1.11), horizontalalignment='center', verticalalignment='center') ax.set_rlim(0,100) ax.grid(True) xticks = np.arange(len(average_score)) #生成x轴每个元素的位置 ax=fig.add_subplot(133) ax.set_xticklabels(name, fontproperties='SimHei') ax.set_xticks(xticks) #设置x轴上每个标签的具体位置 ax.set_ylim([0, 100]) # 设置y轴范围 ax.bar(xticks,average_score,color=bar1_colors) ax.set_title("{} 平均成绩柱状图".format(stu["姓名"]),fontproperties='SimHei') plt.show()2.5 打印全体学生成绩信息这一个功能实现也蛮简单，遍历学生列表，然后调用打印函数逐个进行打印输出即可，这里输出单个学生信息的时候就没有输出统计图的信息了。主要是考虑到人数过多时，输出图的话，可能会导致速度过慢，影响体验。输出完成后会简单统计一下一共有几个人。2.6 课程成绩统计在统计成绩这个模块中，由于数据在列表中已经是有序的了，所以最高分最低分，中位数的获取都比较容易。而平均分也可以很快得出。（其实我觉得，程序的整体结构和思路做好以后，功能模块的实现就方便得多了。）同样地，在这里我也做了一个图形的统计，利用柱状图展示了各个分数段的人数，方便老师快速了解成绩的分布情况。然后利用了饼状图分析了`及格人数/不及格人数`的比例，因为在这里不及格的人数为0，所以整块都是及格的蓝色。画图的代码如下（有了上一张图的经验，这张就好多了）：## 绘制统计试图 def print_statistics_view(stu_list): ##### 数据设置 range_number = [0,0,0,0,0] #各分数段人数 type_number = [0,0] # 各类型人数[及格,不及格,缺考] for stu in stu_list: count_type(stu, type_number) count_range(stu, range_number) #### 开始绘图 fig = plt.figure(figsize=(8, 4), dpi=85) #整体图的标题 colors = ['#7199cf', '#4fc4aa', '#00BFFF', '#FF7F50', '#BDB76B'] #①在121位置上添加柱图，通过fig.add_subplot()加入子图 ax = fig.add_subplot(121) ax.set_title('各分数段人数统计', fontproperties='SimHei') #子图标题 xticks = np.arange(len(range_number)) #生成x轴每个元素的位置 bar_width = 0.5 #定义柱状图每个柱的宽度 #设置x轴标签 score_range = ['[0,60)','[60,70)','[70,80)','[80,90)','[90,100]'] ax.set_xticklabels(score_range) ax.set_xticks(xticks) #设置x轴上每个标签的具体位置 #设置y轴的标签 ax.set_ylabel('人数', fontproperties='SimHei') ax.bar(xticks, range_number, width=bar_width, color=colors, edgecolor='none') #设置柱的边缘为透明 #②在122位置加入饼图 ax = fig.add_subplot(122) ax.set_title('及格\不及格占比') # 生成同时包含名称和速度的标签 type_labels = ['及格','不及格'] pie_labels = ['{}:{}人'.format(type_name, number) for type_name, number in zip(type_labels, type_number)] # 画饼状图，并指定标签和对应颜色 #解决汉字乱码问题 matplotlib.rcParams['font.sans-serif']=['SimHei'] #使用指定的汉字字体类型（此处为黑体） ax.pie(type_number, labels=pie_labels, colors=colors, autopct='%1.2f%%') ax.axis('equal') #保证饼图不变形 plt.show()2.7 保存学生信息到文件中在保存到文件时，默认保存到程序目录下的data_file目录里面，用户可以手动输入文件名，也可以直接回车使用默认选项（防止用户懒得输入这么麻烦的东西^_^）。# 文件头 STUDENT_LABEL = ['序号','姓名','学号','分数','排名','作业1','作业2','作业3','作业4', '测验1', '测验2', '实验1', '实验2'] FILE_DIR = './data_file/' #保存文件的目录，默认为当前文件下的data_file目录 # save to file保存到文件 def save_to_file(stu_list): print("\033[34m",end='') fn = input("请输入文件名(例如: a.csv, 直接回车则默认为[学生成绩信息.csv]) >> ") print('\033[0m',end='') if fn == '': # 默认选项 fn = '学生成绩信息.csv' elif len(fn) < 5: # 该用户没有输入后缀名 fn = fn + '.csv' elif fn[-4:] != '.csv': # 该用户没有输入后缀名 fn = fn + '.csv' all_values = [] for index, stu in enumerate(stu_list): ''' 一个stu字典实体序列化成我们想要的格式，便于保存到文件 index为保存到文件后该实体的序号，与list的序号对应 ''' stu_value = [index, stu['姓名'], stu['学号'], stu['分数'], index+1] stu_value = stu_value + stu['作业'] + stu['测验'] + stu['实验'] all_values.append(stu_value) with open(FILE_DIR+fn,'w+',newline='') as f: writer = csv.writer(f)#创建一个csv的写入器 writer.writerow(STUDENT_LABEL)#写入标签 writer.writerows(all_values) #写入样本数据 f.close() print('\033[1;31m') print("保存信息到["+FILE_DIR+fn+"]成功！") print('\033[0m')用户输入自定义的文件名后，由于保存的是CSV格式的文件，因此需要简单修正一下用户输入的文件名（因为有时候可能没有输入后缀名之类的。），然后再读取列表的数据，保存到文件中，如下：可以看到，由于列表的数据始终是有序的，因此排名与序号是对应的。2.8 从文件中读取学生信息从文件读取信息时，遵循的格式和保存的格式是一致的。与从文件中添加信息不同的是，该功能读取文件中所有的信息添加进一个新的列表，然后丢弃系统原有的列表，使用读取文件生成的新列表。同时，从文件读取信息时，也允许分数项缺失，如果缺失，则重新计算后存入列表中去。导入文件也提供了默认的文件：# 从文件导入信息 # 需要遵循格式：['序号','姓名','学号','分数','排名','作业1','作业2','作业3','作业4', '测验1', '测验2', '实验1', '实验2'] def load_from_file(): print("\033[34m",end='') fn = input("请输入文件路径(例如: C:/a.csv, 直接回车则默认为[./data_file/学生成绩信息.csv]) >> ") print('\033[0m',end='') file_path = FILE_DIR+'学生成绩信息.csv' # 默认选项 if fn != '': file_path = fn stu_list = [] n = 0 with open(file_path) as csvfile: csv_reader = csv.reader(csvfile) # 使用csv.reader读取csvfile中的文件 next(csv_reader) # 跳过文件头 for row in csv_reader: # 读取数据 work = [float(x) for x in row[5:9]] #转化作业成绩 test = [float(x) for x in row[9:11]] #转化测验成绩 experiment = [float(x) for x in row[11:]] #转化实验成绩 score = 0 if row[3] == '': score = calc_score(work, test, experiment) # 考虑到成绩位置为空的情况，重新计算成绩。 else: score = float(row[3]) stu_info = {'姓名':row[1], '学号':row[2], '作业':work, '测验':test, '实验': experiment, '分数':score} stu_list.append(stu_info) # n = n + 1 # 如果读取的是本程序输出的，按理说不用排序 # 但也可能是从其他文件读入的数据，所以还是得做一下排序。 stu_list.sort(key=lambda d:(d["分数"],np.mean(d["作业"]),np.mean(d["测验"]),np.mean(d["实验"])), reverse = True) # 排好序 print('\033[1;31m') print("从文件["+file_path+"]导入成功！共 "+str(n)+" 条信息！") print('\033[0m') return stu_list2.9 退出在退出的时候，我做了一个小提示，提示用户是否保存当前数据到文件中去。因为有时候如果不提醒用户的话，用户可能由于疏忽而忘记了保存到文件，一旦退出程序则数据就丢失了。3小结这个程序断断续续写了好久，主要是想把这个作业给做的完善一些（因为小编有各种强迫症）。尽管这是一个小小的project，但是如果能充分考虑各方面的因素，功能上做到尽可能完美，程序上尽可能做到健壮，也是一件并不简单的事情。当然了，一些元素都是基于我自己个人的简单思考而设计实现的需求，并没有做过相关实际的调研问询，所可能会存在不合理的地方。希望各位读者嘴下留情。如果喜欢的话，各位可以点个在看嘛！
-
发表了文章 2022-04-23
10分钟用Python或MATLAB制作漂亮的甘特图（Gantt）
好久没有更新了，今天趁着放假，赶紧来水一期。嗯没错，就是这么直白。我们做过几个关于生产调度相关的算法，相关的传送门如下：遗传算法求解混合流水车间调度问题（附C++代码）作业车间调度JSP与遗传算法GA及其Python/Java/C++实现Tabu Search求解作业车间调度问题(Job Shop Scheduling)-附Java代码但是说到生产调度，就不得不提甘特图这东西，可以用它来直观看调度的情况，非常方便。比如下图中：Python画Gantt图其实用Python画gantt原理是利用plt.barh()绘制水平方向的条形图，然后加以不同颜色区分表示。就是这么简单的。下面给出一个代码模板：import matplotlib.pyplot as pltimport numpy as npax=plt.gca()[ax.spines[i].set_visible(False) for i in ["top","right"]]def gatt(m,t): """甘特图 m机器集 t时间集 """ for j in range(len(m)):#工序j i=m[j]-1#机器编号i if j==0: plt.barh(i,t[j]) plt.text(np.sum(t[:j+1])/8,i,'J%s\nT%s'%((j+1),t[j]),color="white",size=8) else: plt.barh(i,t[j],left=(np.sum(t[:j]))) plt.text(np.sum(t[:j])+t[j]/8,i,'J%s\nT%s'%((j+1),t[j]),color="white",size=8)if __name__=="__main__": """测试代码""" m=np.random.randint(1,7,35) t=np.random.randint(15,25,35) gatt(m,t) plt.yticks(np.arange(max(m)),np.arange(1,max(m)+1)) plt.show()效果图如下：这里讲讲plt.barh这个函数，官方barh()项目地址如下：https://matplotlib.org/api/_as_gen/matplotlib.pyplot.barh.html?highlight=barh#matplotlib.pyplot.barhbarh()表示绘制水平方向的条形图，基本使用方法为：barh(y, width, left=0, height=0.8, edgecolor)各个参数解析如下：- y：在y轴上的位置- width：条形图的宽度（从左到右的哦）- left：开始绘制的x坐标- edgecolor：图形边缘的颜色还是用图解释方便一点，比如下图【J12 T21】：当然，为了让各个图形更有区分度，你也可以指定边缘的颜色。上面的是生产调度的甘特图。这里再帖一个项目管理的甘特图。是GitHub上的@stefanSchinkel大神（总是大神大神，让我觉得有种营销号的感觉！/哭笑）做的。详情可以戳：https://github.com/stefanSchinkel/gantt东西全都封装好了。只需要下载上述文件中的gantt.py,然后from gantt import Gantt即可使用。✎ 运行环境要求 matplotlib==3.0.3numpy>=1.16.3不过读取数据采用的是json格式的，结构如下：{ "packages": [ { "label" : "WP 1-1", "start": 0, "end": 2, "milestones" : [2], "legend": "worker one" }, { "label" : "WP 1-2", "start": 2, "end": 4, "milestones" : [3, 4] } ], "title" : " Sample GANTT for \\textbf{myProject}", "xlabel" : "time (weeks)", "xticks" : [2,4,6,8,10,12] }- label：表示工作流程的名称- start：开始时间- end：结束时间- milestones：里程碑- legend：标签- title：标题- xlabel：x轴名称- xticks：x轴的刻度标签使用也很简单，比如利用当前目录下的sample.json生成一张甘特图：from gantt import Gantt g = Gantt('./sample.json') g.render() g.show() # or save w/ g.save('foo.png')效果图如下：MATLAB画Gannt图当然MATLAB也是可以画的，具体我这里就不展开说了（因为我很少用这玩意，不太熟悉）。直接给出一个CSDN上@mnmalist大神写的脚本模板：%fileName:mt06_final.mt06 %fileDescription:create a gatt chart whith the data given %creator:by mnmlist %Version:1.0 %last edit time：06-05-2015 clear; axis([0,42,0,6.5]);%x轴 y轴的范围 set(gca,'xtick',0:2:42) ;%x轴的增长幅度 set(gca,'ytick',0:1:6.5) ;%y轴的增长幅度 xlabel('加工时间','FontName','微软雅黑','Color','b','FontSize',16) ylabel('机器号','FontName','微软雅黑','Color','b','FontSize',16,'Rotation',90) title('mk01 的一个最佳调度（最短完工时间为40）','fontname','微软雅黑','Color','b','FontSize',16);%图形的标题 n_bay_nb=6;%total bays //机器数目 n_task_nb = 55;%total tasks //任务数目 %x轴 对应于画图位置的起始坐标x n_start_time=[0 0 2 6 0 0 3 4 10 13 4 3 10 6 12 4 5 6 14 7 9 9 16 7 11 14 15 12 16 17 16 15 18 19 19 20 21 20 22 21 24 24 25 27 30 30 27 25 28 33 36 33 30 37 37];%start time of every task //每个工序的开始时间 %length 对应于每个图形在x轴方向的长度 n_duration_time =[6 2 1 6 4 3 1 6 3 3 2 1 2 1 2 1 1 3 2 2 6 2 1 4 4 2 6 6 1 2 1 4 6 1 6 1 1 1 5 6 1 6 4 3 6 1 6 3 2 6 1 4 6 1 3];%duration time of every task //每个工序的持续时间 %y轴 对应于画图位置的起始坐标y n_bay_start=[1 5 5 1 2 4 5 5 4 4 3 0 5 2 5 0 0 3 5 0 3 0 5 2 2 0 3 1 0 5 4 2 1 0 5 0 0 2 0 3 2 1 2 0 1 0 3 4 5 3 0 2 5 2 0]; %bay id of every task ==工序数目，即在哪一行画线 %工序号，可以根据工序号选择使用哪一种颜色 n_job_id=[1 9 8 2 0 4 6 9 9 0 6 4 7 1 5 8 3 8 2 1 1 8 9 6 8 5 8 4 2 0 6 7 3 0 2 1 7 0 4 9 3 7 5 9 5 2 4 3 3 7 5 4 0 6 5];% rec=[0,0,0,0];%temp data space for every rectangle color=[1,0,0; 0,1,0; 0,0,1; 1,1,0; 1,0,1; 0,1,1; 0.67,0,1; 1,.5,0; .9,.5,.2; .5,.5,.5];%和上一个版本的最大不同在于,matlab中仅可以用字符表示8种颜色，超过8种就不可以了，现在用rgb数组可以表示任意多的颜色 for i =1:n_task_nb rec(1) = n_start_time(i);%矩形的横坐标 rec(2) = n_bay_start(i)+0.7; %矩形的纵坐标 rec(3) = n_duration_time(i); %矩形的x轴方向的长度 rec(4) = 0.6; txt=sprintf('p(%d,%d)=%d',n_bay_start(i)+1,n_job_id(i)+1,n_duration_time(i));%将机器号，工序号，加工时间连城字符串 rectangle('Position',rec,'LineWidth',0.5,'LineStyle','-','FaceColor',[color(n_job_id(i)+1,1),color(n_job_id(i)+1,2),color(n_job_id(i)+1,3)]);%draw every rectangle text(n_start_time(i)+0.2,(n_bay_start(i)+1),txt,'FontWeight','Bold','FontSize',16);%label the id of every task ，字体的坐标和其它特性 end效果图如下：看起来也还行（花里胡哨的）。。。好了，以上，这就是今天的内容介绍。
-
发表了文章 2022-04-23
Python中利用Matplotlib绘制多图并合并展示
大家好，最近在研究在搞Python的大作业，有个需求就是利用Matplotlib画几个像模像样的统计图然后合并在一张图中，因为此前很少用这方面的东西，所以折腾了不少时间，今天介绍一下。1subplot多合一其实，利用python 的matplotlib包下的subplot函数可以将多个子图放在同一个画板上。在此之前，我们先来看一个案例：import matplotlib.pyplot as plt import numpy as np plt.rcParams['font.sans-serif']=['SimHei'] # 用来正常显示中文标签 plt.rcParams['axes.unicode_minus']=False # 用来正常显示负号 t=np.arange(0.0,2.0,0.1) s=np.sin(t*np.pi) plt.figure(figsize=(8,8), dpi=80) plt.figure(1) ax1 = plt.subplot(221) ax1.plot(t,s, color="r",linestyle = "--") ax2 = plt.subplot(222) ax2.plot(t,s,color="y",linestyle = "-") ax3 = plt.subplot(223) ax3.plot(t,s,color="g",linestyle = "-.") ax4 = plt.subplot(224) ax4.plot(t,s,color="b",linestyle = ":")效果如下：可以看到，一个画板上放了4个子图。达到了我们想要的效果。好了我们现在来解析一下刚刚的部分代码：plt.figure(1)：表示取第一块画板，通俗地讲，一个画板就是一张图，如果你有多个画板，那么最后就会弹出多张图。plt.subplot(221)：221表示将画板划分为2行2列，然后取第1个区域。那么第几个区域是怎么界定的呢？这个规则遵循行优先数数规则！比如说4个区域：优先从行开始数，从左到右按顺序1234……然后再下一行。那么下面这几行代码大家都懂了吧：ax1 = plt.subplot(221) ax1.plot(t,s, color="r",linestyle = "--") ax2 = plt.subplot(222) ax2.plot(t,s,color="y",linestyle = "-") ax3 = plt.subplot(223) ax3.plot(t,s,color="g",linestyle = "-.") ax4 = plt.subplot(224) ax4.plot(t,s,color="b",linestyle = ":")一共划分了2X2=4个区域，然后1234分别开始绘图。so easy！比如我们想达到下面的效果：那么只需要：import matplotlib.pyplot as plt import numpy as np plt.rcParams['font.sans-serif']=['SimHei'] # 用来正常显示中文标签 plt.rcParams['axes.unicode_minus']=False # 用来正常显示负号 t=np.arange(0.0,2.0,0.1) s=np.sin(t*np.pi) plt.figure(figsize=(8,8), dpi=80) plt.figure(1) ax1 = plt.subplot(221) plt.plot([1,2,3,4],[4,5,7,8], color="r",linestyle = "--") ax2 = plt.subplot(222) plt.plot([1,2,3,5],[2,3,5,7],color="y",linestyle = "-") ax3 = plt.subplot(212) plt.plot([1,2,3,4],[11,22,33,44],color="g",linestyle = "-.")子图1和子图2与上面的一样，主要是子图3，plt.subplot(212)表示将整个画板分成两部分后取第2块，即下面的部分。2subplot2grid分格显示这种方式和上一种实现的效果一样，只不过更加容易理解罢了，先来看一个案例代码：import matplotlib.pyplot as plt import numpy as np plt.rcParams['font.sans-serif']=['SimHei'] # 用来正常显示中文标签 plt.rcParams['axes.unicode_minus']=False # 用来正常显示负号 #method1: subplot2grid ########################### plt.figure(figsize=(12, 10), dpi=80) ax1=plt.subplot2grid((3,3),(0,0),colspan=3,rowspan=1)#相当于格子分成3行3列,列跨度为3，行跨度为1 ax1.plot([1,2],[1,2]) #轴的范围，x轴，y轴。 ax1.set_title('ax1_title') ax2=plt.subplot2grid((3,3),(1,0),colspan=2,rowspan=1) ax2.plot([2,4,6],[7,9,15]) ax3=plt.subplot2grid((3,3),(1,2),colspan=1,rowspan=1) x = np.arange(4) y = np.array([15,20,18,25]) ax3.bar(x,y) ax4=plt.subplot2grid((3,3),(2,0),colspan=1,rowspan=1) ax5=plt.subplot2grid((3,3),(2,1),colspan=2,rowspan=1)效果如下：结合图可能更好理解一点，其中代码：plt.subplot2grid((3,3),(0,0),colspan=3,rowspan=1)第一个参数(3,3)相当于格子分成3行3列,第二个参数(0,0)表示该子图的开始位置，colspan=3表示子图的列跨度为3，rowspan=1表示子图的行跨度为1。好了，以上就是Matplotlib绘制多图的内容，是不是很简单呢！喜欢的小伙伴可以收藏一下，万一哪天就用得上了呢。- End -参考资料：python笔记：matplotlib的简单快速入门之多图合并(2)https://blog.csdn.net/abc13526222160/article/details/85276736Matplotlib的子图subplot的使用https://www.jianshu.com/p/de223a79217a使用matplotlib:subplot绘制多个子图https://blog.csdn.net/dpengwang/article/details/85058026
-
发表了文章 2022-04-23
干货 | Python人工智能在贪吃蛇游戏中的应用探索（上）（三）
强化学习Q_LearningQ_learning是一个基于值的强化学习算法，利用 Q 函数寻找最优的「动作—选择」策略。强化学习是机器学习的一个分支，是指在某个环境下，一个个体通过和环境的互动，而不断改进他行为的方法。最常见的强化学习的例子就是我们经常玩的游戏，比如贪吃蛇游戏，在这个游戏中，输入的内容是：状态(States)=环境，贪吃蛇的蛇头的位置，食物的位置；动作(Actions)=任何可以执行的操作，上下左右的移动；奖励(Rewards)=每个动作得到的奖励，吃掉食物得到的分数，蛇死掉扣掉的分数等；输出的内容：方案(Policy)=在当前状态下，应该选哪个行动。它是一个状态到一个行动的函数。(S,A,R)是用户输入的，P是函数生成的。以上4个元素通过tuple方法定义结构，tuple(S,A,R,P) 构成了强化学习系统。Q_learning 的目的就是最大化Q函数的值（给定一个状态和动作时的未来奖励期望），贪吃蛇走怎么样的路线，才能得到最高的分数。对于在每个状态下的每个动作产生的结果（得到的分数），我们可以用下面的表这里，我们引入一个路径规划的概念: Bellman condition, 这个概念的中心思想是说：如果从最佳选择的路径的末端截除一小部分，余下的路径仍然是最佳路径。举例：有个最优路径经过了ABCDE五个点，那么BCDE路径肯定是最优的。所以，我们想获得最优的路径，只需要获得每个分割成的更短路径的最优解。上图是最简单的Q_table的例子， Q-table是Q-learning的核心。它是一个表格，每一列代表一个动作，每一行表示一个状态。则每个格子的值就是此状态下采取此动作获得的最大长期奖励期望。通过此，就可以知道每一步的最佳动作是什么。将这个概念用到寻找最佳路径上称作temporal difference learning。为便于计算，将Q-Table表示为Bellman递推等式，拆分为当前回报和未来最大回报的和，即，其中表示状态在行为作用下的下一状态，而为状态后所有可能的行为，为价值累积过程中的打折系数，决定了未来回报相对于当前回报的重要程度。在训练过程中，初始为0，训练中每行动一次，通过Bellman等式计算，优化目标是使得Agent根据Q函数执行动作能获得训练过程中的最大价值回报，即与的差异最小。我们的训练步骤是：首先我们设置一个探索速率「epsilon」，它的值在0和1之间。一开始时候我们将它设定为1。它处于最大值，因为我们不知道 Q-table 中任何的值，所以我们需要走出随机的行动。随着训练次数的增加，我们将会进行借助前面训练得到的经验，于是我们逐渐减小「epsilon」值，做到探索和贪心的平衡。选择了动作Action后， 并且观察输出的状态和奖励。接着我们使用Bellman方程去更新，：Q_learning 训练过程如上图所示，推荐给大家我看到的两张有趣的图，可以更清楚的理解Q_Learning.Deep Q-Learning深度学习在前面介绍中，我们用矩阵来表示，但是在现实情况下，这个只是个理想状态，因为状态实在是太多。使用表格的方式根本存不下，那么怎么处理遇到的上面的问题呢？对于如同贪吃蛇或者更复杂的场景这种情况，需要输入的state包含的信息会很多(高维)，而输出的内容比较少(低维，比如上下左右）。这种情况又怎么处理呢？Q-learning无法解决的这些问题，而被与神经网络结合的DQN完美的解决了。DQN和Q_learning相比，还有突出的几个改进:1) DQN使用了卷积神经网络来逼近行为值函数什么是价值函数近似呢？说起来很简单，就是如果用一个函数来表示Q(s,a)。理论上对于任意的(s,a)我们都可以由公式求出它的值函数。但是当state或action的个数过多时，分别去求每一个值函数会很慢。因此我们用函数近似的方式去估计值函数，这样，对于未在Q_Table中出现的state action也可以估计值函数。值函数网络与贪心策略之间的联系是这样的：首先环境会给出一个state，根据值函数网络得到关于这个state的所有Q(s,a)，然后利用贪心策略选择action并做出决策，环境接收到此action后会给出一个奖励Rew及下一个state。这是一个step，此时我们根据Rew去更新值函数网络的参数，接着进入下一个step。如此循环下去。最优化一个损失函数loss function，也就是标签和网络输出的偏差，目标是让损失函数最小化。然后我们用Q_table处理巨量的有标签数据，然后通过反向传播使用梯度下降的方法来更新神经网络的参数。2) DQN 设计了memory储存经验，并利用经验回放训练强化学习过程由于在强化学习中，我们得到的观测数据是有顺序的，用这样的不独立数据使整个网络局限于一小块状态区域，用它们去更新神经网络的参数有很大的局限性，为了得到独立的数据, 用一个Memory来存储经历过的数据，每次更新参数的时候从Memory中随机抽取一部分的数据来用于更新，这样打破数据间的关联。3) DQN的探索在开始训练的时候，所有的参数都是随机的，有最高Q值的Action也是随机的，这是神经网络刚开始的探索过程。但是随着训练次数的增加，随着Q值的收敛，选择的Action会趋于一致。这时候，我们选择一个合适的概率，使一部分Action不按照最大Q值行动，也就是寻找一个好奇心和贪婪心之间的平衡。这个概率一般是从开始训练时的1逐步减少到0.1。也就是说开始训练拥有最大的好奇心，然后逐步向利用经验侧重。4) 引入了一个target Q网络为了解决这个问题， DQN在原来的Q网络的基础上又引入了一个target Q网络，即用来计算target的网络。它和Q网络结构一样，初始的权重也一样，只是Q网络每次迭代都会更新，而target Q网络是每隔一段时间才会更新。下图是DQN的基本架构DQN的基本架构DQN的基本算法流程:首先初始化Memory，定义它的容量为D；初始化本地神经网络和目标神经网络，随机生成权重，本地神经网络和目标神经网络的权重相同；循环遍历训练次数episode =1, 2, …, M；初始化环境变量；循环遍历step =1,2,…, T：用贪心策略生成action执行action 计算得到的分数，获取next state；分action后是terminal和不是terminal两种情况计算reward；对模型权重使用梯度下降法进行更新；每经过N步，对目标模型进行更新；将相应内容存入memory中（state, action, reward, next state）利用DQN开发的贪吃蛇程序说明：为了更快地学习和验证DQN在贪吃蛇程序中的应用，我借鉴了齐浩洋学长的源代码。为了程序的呈现效果，我把部分源程序（训练部分）重新组合了一下，并将原来的程序里的各个模块进行了一下整合。此处，先介绍贪吃蛇训练的过程，完整的程序在后续推文中进行介绍。贪吃蛇训练的过程（DQN实现方法）** 注：在本例中每个批次取出的数据 self.BATCH_SIZE=64 For.. to 迭代次数 #环境初始化 # ... # 蛇，食物位置；界面大小，边界位置 # while 贪吃蛇 处于活的状态 每次循环是走一个step. # memory 中如果有足够的样本，则随机取出批次量的数据。 if self.memory.__len__() > self.BATCH_SIZE： # experiences = random.sample(self.memory, k=self.BATCH_SIZE) #提取反馈信息 取出的每个变量为长度为64的数组,18是state组合的环境因素个数. states（当前状态 tensor[64,18]）, actions（动作 tensor[64,4]）, rewards(分数), next_states（下一状态, tensor[64,18]）, dones（是否活着） = zip(*experiences) #设置本地模型和目标模型（解决参数不收敛的问题) #使用本地模型估计下一个动作 target 为tensor(64,4) target = self.qnetwork_local.predict(states, self.BATCH_SIZE) #使用目标模型估计下一个动作。 target_val = self.qnetwork_target.predict( next_states, self.BATCH_SIZE) target_next = self.qnetwork_local.predict( next_states, self.BATCH_SIZE) #Double DQN需要从中取出有最大值的下一步做为action max_action_values = np.argmax(target_next, axis=1) #计算target 的奖励分数(或许样本的最大分数） for i in range(self.BATCH_SIZE)： if dones[i]： target[i][actions[i]] = rewards[i] else： target[i][actions[i]]= rewards[i] + self.GAMMA target_val[i][max_action_values[i]] # 训练模型 对本地模型权重进行更新 self.qnetwork_local.train( states, target, batch_size=self.BATCH_SIZE) # 每训练UPDATE_EVERY次更新目标模型的权重 目标模型不是每次都进行更新，保持参数的收敛。 if self.t == self.UPDATE_EVERY： self.update_target_weights() self.t = 0 else： self.t += 1 #按照训练选择下一步 （代码3，随机走出随机的动作，使样本内容更加全面) state = state.reshape((1,)+state.shape) action_values = self.qnetwork_local.predict(state) if random.random() > epsilon： #选择最好的行动 action = np.argmax(action_values) else： #选择随机的行动 action = random.randint(0, self.nA-1) #在环境中走下一步，并且判断贪吃蛇是否触发死的条件 ...... if 死掉 break； #将经验存入memory self.memory.add(state, action, reward, next_state, done) Endfor系统设置参数，循环进行上述训练，从环境初始到贪吃蛇死掉.为一个过程。系统训练这个过程多次，训练结果放入****.h文件中。下图为贪吃蛇训练部分的程序运行展示：上述就是人工智能贪吃蛇的基本入门知识，希望对大家有所帮助，后续，我还会进一步完整的分析代码，方便大家理解。
-
发表了文章 2022-04-23
干货 | Python爬虫实战（中）：数据可视化-教你做出漂亮的图表
前言各位看客老爷们，我又来啦。上一期我们利用Python+百度地图POI抓取了一些高校之间的距离数据，传送门：干货 | Python爬虫实战：两点间的真实行车时间与路况分析（上）不知道上一期的爬取数据的内容大家都品尝的怎么样了呢。今天给大家带来的是python中对数据进行可视化处理的内容。可能大家并不是很懂这个可视化的意思，大家可以先在脑海里面脑补一下那种酷炫的数据分析图，脑补出来了吗？嘿嘿，用Python究竟能做一些什么样的图表呢，可以肯定的告诉大家，只有你想不到，没有它做不到！吊了半天胃口，现在上图！直角坐标系动态散点图直角坐标系柱状图3D柱状图地图对，我们要做的图就是和上面这几张图片一样！酷吧？上面的效果图都是我们今天要介绍的主角pyecharts库制作的！当然，pyecharts的作图类型肯定不仅仅只有上述这些图形，它还有很多很多类型，在这里我就不多说了。在这一期推文中呢，我们主要介绍的是第一种图形，柱状图的使用。目录pyecharts模块的下载模型的建立数据的导入图形的生成加点更炫的写在最后pyecharts模块的下载要使用这个模块，你必须要下载这个模块，打开自己电脑的cmd，输入pip install pyecharts就可以了，如果本来就有这个模块的话，就不用下载了。当然，如果电脑没有pip这个模块的话，需要自己去下载一个这个模块，在后续的推文中，小玮会给大家带来一些python的基本配置应该做的相关推文，帮助大家解决python的安装问题。在安装这个模块之后，我们就可以在编译器中引用这个模块了。from pyecharts.charts import Bar这里的Bar是柱状图的意思。pyecharts的库里面有很多很多东西，我们没有必要全部引用，那样会让本来简单的程序运行起来忒慢。模型的建立引入了这个模块当然还不够，我们还需要数据。数据的导入大家还记得我们上一篇推文中生成的csv文件吗？如果已经忘了，请回去再看看上一篇推文，然后运行程序把相应的csv文件生成出来。那么，我现在就认为大家已经有这个csv文件了。在一个程序中，我们想要获得一个文件的数据，需要做什么？想一想。没错，就是读取这个文件。那么大家还记得读取这个文件怎么办吗？没错，就是加入pandas模块，运用pandas的函数来进行文件的读取。import pandas as pd具体怎么读取呢？和之前的也是一模一样。path_data=pd.read_csv(r'F:\my python\123.csv')这些在上一篇推文中都已经很详细的介绍过了，这一次就不多说了。要是忘了记得回去看看奥-图形的生成做好了这些之后，我们正式的来介绍一下建立柱状图这个函数。第一步，定义一个变量是bar型变量。bar=Bar()这一句代码的意思就是使bar为Bar型变量。接下里就是为这个变量赋x轴值和y轴值。bar.add_xaxis(path_data['地点'].tolist()) bar.add_yaxis('用时',path_data['time'].tolist()) bar.add_yaxis('距离',path_data['distance'].tolist())让我们一句一句研究代码。第一句，函数为add_xaxis（），就是添加x轴数据，给x轴添加什么数据呢？Path_data中的‘出发时间’这一列数据。在这个位置我们要注意，划重点，一定要注意，在后面加上.tolist()。因为path_data是最开始读取csv文件的，里面的数据储存形式和csv形式保持一致，所以我们要把她转化为python中列表的形式，即使用.tolist这个函数，否则的话在这个位置添加x轴值是不起任何作用的。现在有了第一句的基础，理解第二句就不困难了，但是x轴和y轴的赋值形式任然有一些差别，这是为什么呢？其实这是给我们赋的y值起一个名字，当然这个位置不起名字也可以，但是如果如果你有多个y值的时候就会产生意思分歧。这是啥意思？看下面的图就知道了。Pyecharts是支持使用多个y值的。比如这个图里面，我们就使用了商家A和商家B两个y值名称，为了便于分辨，所以我的建议是取一个名字。在最后，x值赋好了，y值赋好了，输入代码。bar.render()即可在当前python文件所在的目录下面看到一个html文件，点进去就可以看到我们所制作的图表了。当然括号里面还可以填生成文件的名字和生成的地址，这些都是可以修改的。因为当前我们只需要生成这一个文件，当前目录下也没有别的render文件，所以我们就省略了这个步骤。现在回到我们当前的文件，打开新生成的文件，就可以看到我们刚刚做的图表啦。刚刚生成的图但是，大家看到自己的图表是不是感觉有一点空荡荡的，不够酷炫？不要着急，继续往下面看，我们还有进阶教程~加点更炫的想要使用更加酷炫的功能，我们需要再加入两个模块。from pyecharts import options as opts # 导入配置模块 from pyecharts.globals import ThemeType这两个模块是pyecharts专门提供给使用者对图表进行进一步完善。比如说，你对这个图表的整体颜色有要求，不想是原来的白色，你可以在最开始建立bar的时候这样写。bar=Bar(init_opts=opts.InitOpts(theme=ThemeType.PURPLE_PASSION,width='1280px',height='720px'))Init_opts=opts.InitOpts()函数是给这个图表设置一些初始参数，比如说背景的颜色，分辨率等等的。想设置主题色就用以下代码。theme=themeType.xxxx这个xxx就是主题的颜色，我在这里写的是紫色，当然还有其他的颜色，看客老爷可以自己去官网进行了解。后面分辨率的参数看客老爷可以根据自己需要进行调整。这些是在建立图表的时候进行的一些配置，那么在输入数据以后，我们可以进行哪些步骤？bar.set_global_opts(title_opts=opts.TitleOpts(title='武汉各高校之间的距离与乘车所需时间',subtitle='副标题' ),xaxis_opts=opts.AxisOpts(axislabel_opts=opts.LabelOpts(rotate=60)),datazoom_opts=[opts.DataZoomOpts()])我们可以使用set_global_opts函数进行我们所需要的个性化设置。比如说主标题啊，副标题啊，x值的旋转角度啊，是否有滑块，等等配置。那实例给大家举一下例子看看这些具体指的什么。主副标题在这个图表中左上角的就是我的主标题，下面的就是我的副标题。x值的旋转角度X值倾斜的角度我们在这个图片里也可以很清晰的看出来，当前旋转的角度是60度，这个角度的旋转范围是-90°到90°。滑块功能滑块就在最下面，那个可以滑动的东西。因为有的时候可能数据太多，放在一个页面里看起来太拥挤，这是我们可以用滑块这个功能，使得我们的图形更加分散，便于观察。最终的效果写在最后当然，关于pyecharts的使用实例还有很多很多，各位看客老爷如果有兴趣可以自己去pyecharts的官网进行学习，这个项目是百度研发的，官网是中文的，还有十分详细的教程免费提供，所以小玮在这里就不多说了。在这个位置，我们已经完成了数据的爬取和做成图表。当然，这和老师吩咐的任务完成还有一定的距离，我们没有统计时间，因为最近由于肺炎，道路没有发生拥堵，统计时间发现并没有明显的变化，最终结果趋于一根平行x轴的直线。所以就不在这里讲解时间的统计和回归分析的步骤了。等一切恢复正常了以后，会专门再写一篇推文介绍。最近的肺炎如此严重，各位看客老爷们一定要注意防护！跟着小玮，带你一步一步走进数据结构和爬虫的世界。代码可以在后台回复 PC02 获取
-
发表了文章 2022-04-23
干货 | Python爬虫实战：两点间的真实行车时间与路况分析（二）
制作excel表格为了方便我们对数据进行处理，我们选择将数据存入到excel表格之中。相应时间的获取坐标获取好了之后，我们还需要回到开发文档，再选取Web服务API，进入后再选择批量算路服务。通过这一项服务，我们可以获得目标路段当前时刻下的指定交通方式所花费的时间。进入了以后，就可以看到这一项服务明确的要求了要使用IP白名单检验，这也就是为什么我们在创建应用的时候设置IP白名单检验。在简介中也给出了我们能够通过坐标获取两点之间的距离，行车，步行以及骑行所需要的时间，这个是实时的，会结合实时的交通状况。在服务指南中，详细地给出了我们想要获得目标内容的方法。在这里简单的解释一下为什么无论起点坐标还是终点坐标都是两个坐标。其实很好理解。因为在正常情况下一个地点他不会是一个点，而是一块，而两个点刚好就可以构成一个矩形了。但是在我们这里为了简化操作，地点就简单地认为只有一点，这是一种简化哈，大家在实际复现的时候建议弄两个点。所以我们这次的爬取URL的模式如下。URL=http://api.map.baidu.com/routematrix/v2/交通方式?output=json&origins=起点坐标（先纬度再经度）&destinations=终点坐标&ak=你的AK值。我们现在可以把我们搜索到的点的坐标按照上述样式改一下URL，然后进入这个网页，看看成不成功。如果出现了下面的画面就说明成功了。开始我们的工作做好了前期的准备工作，我们现在正式进入主题。进入目标网页在这个部分，我们会用到一些模块，在这里先拿出来，介绍一下相应的作用。import requests第一个模块顾名思义，就是请求的意思，那么对于我们来说有什么用呢？别急，我们来分析分析，我们进入一个网页的过程。我们打开浏览器，然后输入网址，然后看到我们需要的内容是吧？那么你有没有想过我们为什么需要通过浏览器去访问我们的网页呢？原因很简单，其实就是我们需要浏览器代表我们发送一个请求给我们的URL，然后从URL的服务器再把我们想要的内容反馈给我们，然后我们才能看到。在这个过程中，服务器还给我们一个header，简单的来说就是一个身份证，说明我们是通过合法途径的进入你的网页的，并不是通过非法的途径。分析到这里，小伙伴一定有疑惑，那我们通过requests的时候，怎么证明我们是合法途径呢？那当然是加上一个headers啦。在自己的浏览器中输入about:version。会出现如图所示的画面。我们就可以发现headers就在这里。下面我们尝试着通过request来进行一下自动进入网页。url=xxxx header=xxxx html=requests.get(url,headers=header).text这段代码的主要内容在之前已经说了，这里讲解一下为什么要加入.text。其实就是获取网页中的除了标签以外的内容，因为有可能网站里面还有其他的标签一样的东西，这是构造这个网页是加入的，但是我们并不需要。大家可以尝试，运行这段代码并输出html，可以看到下面的东西:到这里为止，我们已经成功地利用程序进入了目标网页。爬取目标内容import pandas as pd import re解释一下我们当前添加的模块。pandas是一种数组，在这里，我们为什么不使用内置的数组呢？简单的理解就是pandas数组比内置的数组运行速度更快，而且方便我们对文件进行读取。re是一种切割文本的工具，在这里其实如果了解正则表达式的伙伴们应该认识，这个其实就是正则表达式的记号。现在让我们再分析一下，我们从网页中获得的东西，是一长串字符串吧？我们需要什么？只需要里面的极少数的字符吧？其他的我们都不想要。那么我们应该怎么做？是不是应该对字符串进行切割，对的，在这里我们就可以用re模块进行切割。这个函数的基本形式是re.split([分隔符],分割的字符串)。通过对我们所获得的字符串进行观察，找出应该分割的地方的分隔符号，就可以对字符串进行分割。最终结果如下图。容易看出，我们需要的内容所在的下标为19，33。在这里位置为止，我们的工作看似已经完成了，但是我们只是把当前这一段路程的路程和时间记录下来了，还有别的呢？这个时候，我们的pandas数组就出现了。在刚开始的时候，我们就已经把坐标和地址都存到了一个excel文件当中去大家应该都还记得吧。那么我们现在的重点就是围绕这个excel文件展开的。既然我们需要这个excel文件中的东西，那么首先我们需要读取这个excel文件。如何读取呢？这里先放出代码。path_data=pd.read_excel(r'F:\my python\数据\waypath.xlsx') head=path_data['head'] tail=path_data['tail'] position=path_data['position']如上图所示，上面就是pandas读取文件的操作。容易看出，第一段代码就是读取csv文件并存储起来。括号里存放的是我们文件所在的地址，记住一定要在后面加上文件自身的属性，即加上xlsx，这是为了避免在这个地址下存在两个同名但属性不同的文件的矛盾问题。由于python的强大，读取csv文件是按照字典形式存储，后面的head，tail，position就是相应的索引。要注意！前面的r是不可以省略的，因为它是说明在这一行里面出现的\都不是转义符号。在这里我们已经完成了存储操作，伙伴们可以print一下path_data，看看里面的内容。在这里我们可以发现，python中存储数据也是从index为0开始。现在我们已经完成了所有地点和坐标的存储，下面就是循环进行内容的获取和存储的过程了。在这里我们的数据的最后一个下标是27，那么就意味着我们需要循环的次数为28，那么怎么进行这个循环呢？Python中给出了一个非常简单的方式，如下。for i in range(28):这个位置的意思是，依次生成0-27的整数，然后赋给i，这样i在每次循环中对应的值都是相应的次数，基于这个，我们就可以知道后面的循环函数怎么写了。for i in range(28): url='http://api.map.baidu.com/routematrix/v2/driving?output=json&origins={}&destinations={}&ak=S0LC4C1KdAOVGPLcbzlBGL7bLfGz5G1c'.format(str(head[i]),str(tail[i])) html=requests.get(url,headers=header).text html=re.split('[:",}]',html) if i==0: dict_data={'position':[position[i]],'distance':[html[19]],'time':[html[33]]} data=pd.DataFrame(dict_data,columns=['position','distance','time']) else: dict_data =pd.DataFrame({'position': [position[i]], 'distance': [html[19]], 'time': [html[33]]}) data=data.append(dict_data,ignore_index=True) data.to_csv('path_data.csv')看到这个代码，一定很蒙，这都写了些啥啊，咋看不懂？不急，我们一步一步分析。首先是我们对于url的改写，我们把原来存放起点坐标和终点坐标的位置改为了{}，后面加上了.format(str(head[i]),str(tail[i]))这是为什么呢？其实大家从上面读到这里看到代码一定知道这个是为了什么，对，就是为了更新每一次的地址，使她成为excel文件中相应的地址，那么这里{}就和后面的format中的内容进行对应。format具体的用法在这里就不多说了。看客老爷们如果感兴趣可以去查一查，在这里，大家只需要了解是替换相应位置内容就可以了。那么后面我为什么要用if做判断呢？这其实是为了区分当前这个循环是建立一个类似excel一样的变量还是给这个变量里面进行元素添加。I=0时，当然是建立这个变量，I>0时就是添加元素。在这里呢，重点讲解一下下面这一行。pd.DataFrame其实是一个强制转换类型的函数，把刚开始的dict_data转换成DataFrame类型的，为什么要转换呢？转换了有什么用呢？我们转换了其实是为了使用DataFrame类型所特有的一个函数，to_csv，生成csv文件的函数。那么后面的.append()函数大家肯定就明白了，columns是做什么的呢？仔细一看可以发现这个其实和我们DataFrame最开始设的几个索引值是一样的，是的。我们之所以在后面写这个是为了给dataframe进行一个排序，这样在输出这个data的时候她输出的顺序就是colunms里的顺序。在最后一行，意思已经很清楚了，是生成这个csv文件，然后前面patn_data是文件的名字，.csv是文件的属性。data=pd.DataFrame(dict_data,columns=['position','distance','time'])定时操作到这个位置，其实现在我们已经很好地完成了这一次的爬取任务，回到我们的文件夹中，你就可以看到生成的最终csv文件了。但是呢，作为一次数据分析，那么仅仅统计当前这一次的数据肯定是不够的。我们还需要统计很多次来求取平均值。但是我们又不可能看着一个时间就去点一下运行程序，这肯定是不聪明的做法。那么什么是聪明的做法呢？当然是用python自带的函数来做了。这个时候需要添加一个模块。from threading import Timer这个模块就是计时器，为了我们定时运行程序所用的。t = Timer(10, search)t.start()这个函数的具体用法就是Timer（1,2），在1的位置，你需要填写的是你想程序在多久后运行，2的位置为相应的程序，即函数。t.start（）就是计时器开始运行。那么如果我们想要程序规定次数定时的多次运行，我们可以在在相应的函数中放置一个这个Timer函数，进行多次运行。小小的总结好了，本次推文中，着重给大家介绍了如何获取数据，做成csv文件的相关操作。在最后Timer的位置没有详细的讲解，希望大家通过代码进一步了解！在下篇推文中，我们会着重讲述如何建立可视化的曲线。让我们下次再见！
-
发表了文章 2022-04-23
干货 | 自适应大邻域搜索（ALNS）和禁忌搜索（TS）实验对比附代码
前言大家好呀，你们帅气的小编又回来啦！公众号的老观众们应该会记得，在去年这个时候我们公众号发布了有关自适应大领域搜索算法（adaptive large neighborhood search）的相关系列教程，有关传送门如下：1. 干货 | 自适应大邻域搜索(Adaptive Large Neighborhood Search)入门到精通超详细解析-概念篇2. 代码 | 自适应大邻域搜索系列之(1) - 使用ALNS代码框架求解TSP问题3. 代码 | 自适应大邻域搜索系列之(2) - ALNS算法主逻辑结构解析4. 代码 | 自适应大邻域搜索系列之(3) - Destroy和Repair方法代码实现解析5. 代码 | 自适应大邻域搜索系列之(4) - Solution定义和管理的代码实现解析6. 代码 | 自适应大邻域搜索系列之(5) - ALNS_Iteration_Status和ALNS_Parameters的代码解析7. 代码 | 自适应大邻域搜索系列之(6) - 判断接受准则SimulatedAnnealing的代码解析8. 代码 | 自适应大邻域搜索系列之(7) - 局部搜索LocalSearch的代码解9. 自适应大邻域 | 用ALNS框架求解一个TSP问题 - 代码详解当时，为了调用MinGW库，我们还特地做了一份安装教程。但教程中安装库的过程比较繁琐，尤其是对平时习惯使用VS而不是dev C++的观众来说，又要动手下载dev C++，不太方便。对于有点编程基础的同学还好，照着葫芦总能画出一个瓢来：emmm……而对于不熟悉编程的同学而言，一顿操作猛如虎：为了造福人类，这次小编为大家带来了VS版本的ALNS框架，只需要下载处理好的项目文件导入VS中就可以直接运行啦！代码运行习惯使用dev C++的同学，可以直接参考过去的推文，安装MinGW库，再在dev C++上运行。对使用VS的同学，直接从公众号中下载代码，用VS打开.sin文件就行啦！在公众号内输入【ALNSTSPVS】不带【】即可下载相关代码！如图：怎样，是不是跟在床上翻一个身一样简单呢？不过你的VS版本要>=2015哦。这次提供给大家的代码中，除了已经搭建好的ALNS的框架（来自Github，一个法国的PHD写的，原地址：https://github.com/biblik/alns-framework），还有编写的利用ALNS框架求解TSP的代码（代码经过小舟同学修改），并包含几个TSP算例：图中箭头标注的.xml文件用于参数修改。箭头指向的是几个重要参数，用于设置搜索停止条件，分别代表迭代次数、运行时间、未能优化当前解的最大迭代次数。任意一项指标超过设置参数时，程序停止运行：算例在main.cpp中输入，在图示位置输入算例名称：如果要导入自己的算例，将算例放置到工程文件目录下，保证算例格式与所给算例一样，就可以运行啦！简单实验关于ALNS的介绍，过去已经有相关推文做了详细解读。这里我们对ALNS求解TSP的结果进行简单实验，看一看算法的实际运行效果。测试算例采用TSPLIB提供的TSP算例，可以在公众号菜单【资源下载-算例下载】一栏进行下载。我们先将ALNS与Tabu Search进行简单对比，关于Tabu Search的传送门：干货|十分钟快速复习禁忌搜索(c++版)对比结果如下：经过简单的测试发现，ALNS代码运行的时间比禁忌搜索算法更长一些。并且两种算法得出的满意解与最优解都有一些差距，所以我们增加最大迭代次数，看一看两种算法能更精确到什么程度：可以看到,增加迭代次数，ALNS会得到更优的满意解，而TS可能早就陷入了局部最优，已经无法继续得到更优的解了。我们选择算例rd400，进一步测试ALNS的运行情况：从上面的结果可以看出：ALNS通过增加迭代次数，是能更好的逼近最优解的。不过所需要的时间也相应会增加。经过比较可以看出，ALNS收敛的速度较慢，因为其搜索的邻域是非常大的，其达到满意解所需的搜索时间要更久。但正是由于其搜索的邻域巨大，在此过程中不容易过早陷入局部最优，增加搜索时间是有更大概率找到更好的解。而TS搜索的邻域相对ALNS较小（和测试代码的邻域结构有关），不过，这里说的邻域相对较小，并不一定指TS搜索邻域一定比ALNS小，你也可以通过邻域结构的设计，搞得很大很大。但一般而言，ALNS的邻域规模都大一些，毕竟他就是以大规模邻域著称的。在本那次代码中，由于TS只设计了一个邻域算子，因此收敛的速度非常快，但也过早陷入了局部最优。当然，以上测试非常简单，反应出两种算法的不同特点还不够准确，因为实际运行过程建立在代码的基础上，比如对禁忌搜索而言，算子设计的个数、优劣会影响解的精确度；是否进行去重优化会影响搜索速度。对ALNS，代码中设计了local search，因此搜索速度会略慢一些，但优化程度会有所提升。写在后面ALNS相对比较复杂，尤其是我们提供的代码框架非常完善，综合了模拟退火、变邻域搜索的一些特点，要弄清楚并不容易。在接下来的一段时间里，小编也会和大家一起进一步研究ALNS，为大家带来一些ALNS相关的文章，希望大家多多关注~
-
发表了文章 2022-04-23
分享 | C#编写的电影售票系统（附源码+数据库）
最近疫情真的很可怕，大家要注意保护好自己，响应国家的号召。尽量不出门，可以利用这个时间好好充实自己。也希望武汉和中国能尽快好起来，大家都健健康康，相安无事。01 介绍这个是小编上学期的C#课程结课作业，是小组完成的。这次一并分享出来啦。嗯……为什么界面这么少女心呢，并不是小编有一颗少女心，而是因为UI部分是同组的女生负责设计的。我们做的是一个有会员制的电影院购票系统。具有会员注册功能，可区分会员和散客两种身份，实现会员及折扣管理。购票具有挑选电影场次，选择座位和查看电影信息等功能：》查看电影详情、获取排片信息。》选择场次座位，完成支付，获取取票信息。》注册成为影院会员，享受优惠折扣。02 设计思路在功能设计上，一个电影院购票系统，首先需要具备最基础的功能：影片选择、场次选择和座位选择。在用户提交选择后，需要支付模块提示用户付款并完成出票。为了吸引用户，我们增加了会员的注册和登录模块，为会员用户提供折扣。注册与购票的支付我们的处理是预留一个接口，当做简单模拟，实际使用可以调用支付宝或微信的支付接口。在界面设计上，我们为系统添加了好看的背景图片。通过Detail栏展示用户信息与折扣，通过Hot Movie栏在最吸引眼球展示热映电影的海报，提高用户的购买欲望。最后，作为主要部分的座位选择栏简介明了，座位之间间隔明显，有效的防止用户错误操作。03 具体设计通过三层架构来完成影院购票系统的开发，将真个业务应用划分为：界面层（UI层）、业务逻辑层（BLL层）、数据访问层（DAL层）。对于复杂的系统分层让结构清晰，便于对系统进行整体的理解、把握；而且便于维护，将各部分之间的相互影响的程度降低到最小，系统基本的架构可以通过工具自动生成代码。当数据库发生改变时，只用重新生成代码，改动业务逻辑层的部分代码即可。在实施的过程中，难点在于将三层结构进行划分，掌握各层之间的设计思路以及调用关系，下面内容就结合代码展示具体实现过程。1) Model层这层的作用是封装数据，使数据在三层中传输。例如Movie：namespace Model { public class Movie { [Key] public int MovieID { get; set; } public string MovieName{ get; set; } /// 电影名称 public string Actor { get; set; } /// 主演 public string Director { get; set; }/// 导演名 public int Duration { get; set; } //时长 public string MovieType { get; set; }/// 电影类型 public string Poster{ get; set; } /// 海报图片名 } }2) DAL层这一层提供基本的数据访问，实现代码（以Movies为例）：namespace DAL { public class MovieDAL { public static List<Movie> GetAllMovies() { var MoviesQuery = from m in CinemaDbContext.CDbContext.Movies select m; return MoviesQuery.ToList(); } public static Movie GetMovieByMovieID(int mID) { return CinemaDbContext.CDbContext.Movies.Find(mID); } } }3) BLL层这一层负责处理业务逻辑，在本次的系统开发中，包括了与用户和影票信息相关的处理。实现代码（以TicketBLL为例）：namespace BLL { public class TicketBLL { public static bool AddTickets(List<Ticket> tickets) { return true; } } } 4) UI层这一层负责显示和采集用户操作。系统总共包含五个界面，分别为：用户登录界面、用户注册界面、影院主页、票务信息确认界面、支付界面以及取票信息界面。同时，使用Winform皮肤插件来实现对系统界面整体风格的把控。下面将以界面的为单位来对其实现过程进行描述：》用户登录界面用户将身份信息写入文本框后，用其输入的信息创建新的customer对象，通过调用BLL层的功能将输入内容与用户信息比对，最后用判断语句激活弹窗反馈登陆结果，登陆成功后进入到售票系统首页。同时，用户可以点击注册按钮，跳转到注册界面完成新用户的注册。》用户注册界面用户将身份信息写入文本框后，用其输入的信息创建新的customer对象，通过调用BLL层的服务将新的用户信息写入数据库，最后用判断语句激活弹窗对注册结果予以反馈。》主界面排片详情通过TreeView控件进行展示。影厅通过多个CheckBox组成，主要是为了能让用户一次性购买多张票。》购票信息确认界面在选定座位后，进行系统进行核算总的金额，然后显示所选座位信息以及应付的价钱。提示用户是否进行付款。》支付界面获取购票信息，计算总票价，提示支付，显示支付的二维码等并判断是否支付成功。》取票信息界面包括取票二维码以及取票序列号的实现，支付成功后弹出取票码。04 数据库设计数据库采用的是SQLSERVER，可以复制下面的脚本到查询框执行，即可得到数据库和样本数据。系统中采用DbContext方式直接连接数据库。一个DbContext映射了所有的数据库表。具体代码如下namespace Model { public class CinemaDbContext : DbContext { public static CinemaDbContext CDbContext = new CinemaDbContext(); public CinemaDbContext() : base("data source=.\\SQLSERVER1;initial catalog=Cinema;Integrated Security=SSPI;") //构造函数，指定数据库名称的约定连接 { //Code first会在第一次ef查询的时候会对__MigrationHistory访问，是为了检查数据库和model是否匹配，以保证ef能正常运行 Database.SetInitializer<CinemaDbContext>(null); } //public BookDbContext() : base("Data Source=.;Initial Catalog=Students;Integrated Security=SSPI;") { } //DbSet是一个模版类，<>中代表的是模版类中的实体类 public DbSet<Customer> Customers { get; set; } public DbSet<Hall> Halls { get; set; } public DbSet<Movie> Movies { get; set; } public DbSet<Schedule> Schedules { get; set; } public DbSet<Ticket> Tickets { get; set; } protected override void OnModelCreating(DbModelBuilder modelBuilder) { //取消复数表名惯例 modelBuilder.Conventions.Remove<System.Data.Entity.ModelConfiguration.Conventions.PluralizingTableNameConvention>(); } } }各表的设计如下：Customer表：保存注册用户的用户名和密码，建议加密后保存。Hall表：保存每个影厅的信息，包括一行的座位数和一列的座位数。Movie表：保存电影的信息，电影名，类型，演员等。Schedule表：保存电影院的排片信息，包括价格，放映时间等。Ticket表：保存电影票的信息，包括排片信息，具体座位等。》数据库脚本TIP：直接复制源代码说明文件中的数据库脚本到SQLSERVER中执行即可得到数据库和相应的数据。调整一下代码即可连接到程序中使用。脚本文件附录在源代码的README文件最后。
-
发表了文章 2022-04-23
干货|蚁群算法求解带时间窗的车辆路径规划问题详解（附Java代码）
学 习 警 告一眨眼春节又过去了，相信很多同学也和小编一样，度过了一段时间相对轻松的时光。当然，玩耍过后也不能忘记学习。本着~造福人类~的心态，小编又开始干活，为大家带来 有 · 趣 的干货算法内容了！本期为大家带来的内容是蚁群算法，解决大家熟悉的带时间窗的车辆路径规划问题。关于蚁群算法，公众号内已经有相关内容介绍TSP：干货 | 十分钟快速搞懂什么是蚁群算法(Ant Colony Algorithm, ACA)（附代码）本文主要分为以下部分：蚁群算法简介蚁群算法与VRPTW代码测试笔记总结01蚁群算法简介蚁群系统(Ant System或Ant Colony System)一种群体仿生类算法，灵感来源于在蚂蚁觅食的过程。学者们发现，单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为，例如可以在不同的环境下找到到达食物源的最短路径。经进一步研究发现，蚂蚁会在其经过的路径上释放一种可以称之为“信息素”（phenomenon）的物质，蚁群内的蚂蚁对信息素具有感知能力，它们会沿着信息素浓度较高路径行走，而每只路过的蚂蚁都会在路上留下信息素。这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。 蚁群算法通过模仿蚂蚁“每次在经过的较短路径上留下信息素”的行为，通过信息素记录下较优结果，不断逼近最优解。02蚁群算法与VRPTWVRPTW在之前的推文里已经提到过多次了，这里不再详细介绍。感兴趣的朋友可以看过去的推文： 禁忌搜索算法求解带时间窗的车辆路径规划问题详解（附Java代码）通过上面的介绍，大家不难想到，蚁群算法的关键在于信息素的利用。在蚁群寻找食物时，每次都由一只蚂蚁从头开始寻找（不同于禁忌搜索或遗传算法的邻域动作）；每次寻找的不同点在于信息素的改变：不断靠近信息素较浓的路径。用蚁群算法解决VRPTW的过程主要分为以下几步：1.初始化蚂蚁信息（以下用agents表示）；2.为每位agents构造完整路径；3.更新信息素；4.迭代，保存最优解。 算法的关键在第二步：构造解时该如何查找下一个服务的客户。我们用以下公式计算客户j被服务的概率：03代码测试这次代码是由小编亲自编写的，由于是第一次编写ACS的VRPTW代码，有不周之处还请多包涵。因为小编太懒了，具体代码就不在此展示了，有兴趣的朋友可以在公众号内输入【ACSVRP】不带【】即可下载对应Java代码。这里展示一下代码的运行情况。对Solomon Benchmark C101算例的测试效果如下：25点（迭代次数1000，算例最优解191.3）：50点（迭代次数1000，算例最优解362.4）：100点（迭代次数1000，算例最优解827.3）：从测试数据来看，结果似乎不是很好。。。不过，VRPTW仅是一个载体，目的是为了深入了解蚁群算法的运行机制。小编在测试时发现，参数设置地不同对结果还是有一定影响的。算法偶尔会跑出单个点构成的路径，小编认为应该加大时间窗对应参数w_2，效果有一些提升。推荐的参数已经默认设置在代码中。同时，蚁群算法也有其他仿生类算法的特点，比较容易早熟。这点在测试100点数据是尤为明显，全局最优解可能与前100次迭代的最优解相同。04笔记总结大致了解了蚁群算法对VRPTW的求解过程后，我的第一感觉是，和禁忌搜索的思路其实很像：两者都是利用过去搜索的“记忆”指导下一步走向。禁忌禁止一些方向，信息素引导一些方向。但两者又有很大区别：禁忌搜索作为邻域搜索类算法，每次都在旧解里变换出新解；蚁群算法却需要重新派出蚂蚁走完全程。对比之下，每次迭代时蚁群算法可能需要跟更多花费时间。从测试结果来看，蚁群算法确实没有禁忌搜索高效。当然，这可能和小编个人编写代码的能力有关。但不可否认的是，大自然的智慧确实不同寻常，在每一个领域都闪耀着光辉，如此美妙绝伦。（小小的蚂蚁，也蕴藏着让人意想不到的智慧呢！）
-
发表了文章 2022-04-22
作业车间调度JSP与遗传算法GA及其Python/Java/C++实现
大家好呀，好久不见！最近小编接触了遗传算法（Genetic Algorithm）。关于遗传算法，公众号内已经有多盘技术推文介绍：【优化算法】遗传算法(Genetic Algorithm) （附代码及注释）转载 | 遗传算法求解混合流水车间调度问题（附C++代码）今天小编再为大家带来CSDN上一位大牛@sundial dreams关于遗传算法在 作业车间调度问题 上的相关内容，希望大家喜欢！（原文附图）问题描述作业车间调度(Job shop scheduling problem, JSP) 是车间调度中最常见的调度类型，是最难的组合优化问题之一，应用领域极其广泛，涉及航母调度，机场飞机调度，港口码头货船调度，汽车加工流水线等，因此对其研究具有重大的现实意义。科学有效的生产调度不但可以提高生产加工过程中工人、设备资源的高效利用，还可缩短生产周期，降低生产成本。作业车间调度问题描述：一个加工系统有M台机器，要求加工N个作业，其中，作业i包含工序数为L_i。令，则L为任务集的总工序数。其中，各工序的加工时间已确定，并且每个作业必须按照工序的先后顺序加工。调度的任务是安排所有作业的加工调度排序，约束条件被满足的同时，使性能指标得到优化。作业车间调度需要考虑如下约束:1.每道工序在指定的机器上加工，且必须在前一道工序加工完成后才能开始加工。2.某一时刻1台机器只能加工1个作业。3.每个作业只能在1台机器上加工1次。4.各作业的工序顺序和加工时间已知，不随加工排序的改变而改变。问题的数学模型：令(i,j)表示作业i的第j个工序。S_ij和T_ij分别表示(i,j)的加工起始时刻和加工时间。Z_ijk表示(i,j)是否在第k台机器上加工：如果(i,j)在第k台机器上加工，Z_ijk=1；否则，Z_ijk=0，C_k为第k台机器的完工时间，则问题的数学模型如下： 公式(1)为目标函数，即优化目标，系统中使用总加工时间最短为优化目标。公式(2)表示1个作业只能在加工完成前一道工序后才可以加工后一道工序。公式(3)表示1个作业的第1道工序的起始加工时刻大于或等于0。公式(4)表示在1台机床上不会同时加工1个以上的作业。遗传算法随着遗传算法（genetic algorithm (GA)）在组合优化问题的广泛应用，许多人开始对遗传算法进行深度研究。已有研究结果表明，遗传算法对求解作业车间调度问题具有较好的效果，因此系统采用遗传算法来解该问题，遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。系统通过模拟生物进化，包括遗传、突变、选择等，来不断地产生新个体，并在算法终止时求得最优个体，即最优解。遗传算法解决作业车间调度问题基本步骤：1.初始化一定数量的种群（染色体编码）2.计算个体适应度（染色体解码）3.采用锦标赛法选择染色体并交叉产生新个体4.个体（染色体）变异5.达到遗传代数终止算法并从中选取适应度最优的个体作为作业车间调度问题的解流程图如下：遗传算法所需参数：1.种群规模：种群中个体的数量，用populationNumber表示2.染色体长度：个体的染色体的长度，用chromosomeSize表示3.交叉概率：控制交叉算子的使用频率，用crossProbability表示，并且值为0.954.变异概率：控制变异算子的使用频率，用mutationProbability表示，并且值为0.055.遗传代数：种群的遗传代数，用于控制遗传算法的终止，用times来表示遗传算法实现基本步骤及伪代码：1. 编码及初始化种群 采用工序实数编码来表示染色体，即M台机器，N个工件，每个工件的工序数为process_i，则染色体长度为chromosome=process_1+process_2+...，对染色体编码如下：chromosome=...,w_i,w_j,w_k,...其中w_i代表第i个工件编号，而出现的次数代表该工件的第几道工序。例如{0, 1, 2, 1, 2, 0, 0, 1, 2}，中0，1，2表示工件的编号，第几次出现就代表第几道工序。然后将每一次随机生成的染色体个体加入到种群集合中。算法伪代码：2. 解码及计算适应度 将优化目标定义为总加工时间最短，因此适应度定义为最短加工时间的倒数，设fitness为对应个体的适应度，fulfillTime为最短加工时间，因此 其中fulfillTime的计算方法如下：首先定义如下变量然后从左到右遍历个体的染色体序列，其中表示第i个工件的编号，则对应的当前工序为,设为p。当前工件当前工序所使用的机器编号为，设为m。当前工件当前工序对应的加工时间为，设为t。则工件的第p道工序的最晚开始时间为 而第m台机器的加工时间为 工件的第p道工序的结束时间为最后加工完所有工件的最短加工时间fulfillTime为从而计算出适应度fitness。PS.小编觉得解码的过程类似动态规划。伪代码如下：3. 个体选择算子个体的选择使用锦标赛法，其基本策略为从整个种群中随机抽取n个个体让它们竞争，选取其中最优的个体。该算子的选择过程如下伪代码如下：4. 染色体交叉算子使用Order Crossover(OX)交叉算子，该算子的交叉步骤如下：对于一对染色体g1, g2，首先随机产生一个起始位置start和终止位置end，并由从g1的染色体序列从start到end的序列中产生一个子代原型 将g2中不包含在child prototype的其余编码加入到child prototype两侧上述步骤将产生一个child，交换g1, g2即可产生另一个child伪代码如下：5. 染色体变异算子变异的作用主要是使算法能跳出局部最优解，因此不同的变异方式对算法能否求得全局最优解有很大的影响。使用位置变异法作为变异算子，即从染色体中随机产生两个位置并交换这两个位置的值伪代码如下：6. 算法整体伪代码如下：代码实现原作者编写了Java，Python，C++三个版本的代码，小编仔细阅读了Java代码，在其中加入一些注释并略作修改，分享给大家。说明一下输入部分，输入的算例是写死在代码中的，算例如下：Jop0=[(0,3),(1,2),(2,2)]Jop1=[(0,2),(2,1),(1,4)]Jop2=[(1,4),(2,3)]在这个例子中，作业jop0有3道工序：它的第1道工序上标注有(0,3)，其表示第1道工序必须在第0台机器上进行加工，且需要3个单位的加工时间；它的第2道工序上标注有(1,2)，其表示第2道工序必须在第1台机器上进行加工，且需要2个单位的加工时间；余下的同理。总的来说，这个实例中共有8道工序。图中是其中一种可行解。那么本期内容到这里就差不多结束了。下次再见~最后祝愿武汉早日度过难关，小编早就想上学了！武汉加油！
-
发表了文章 2022-04-22
干货 | Python调用百度地图API获取各点的经纬度信息（两种方式）
小伙伴们大家好，在上一期的推文中我们介绍了如何利用百度地图的API获取POI兴趣点的相关信息，详见：干货 | 10分钟教你用Python获取百度地图各点的经纬度信息但是只是简单介绍了API的调用方式。今天我们来讲讲如何在Python里面调用申请的API接口，然后利用Python进行相关的数据处理，最终得到我们想要的信息。最近大家还是要响应号召，不出门！在家好好学习吧~地点检索方式目前百度地图的地点检索服务有以下4种方式：行政区划区域检索：开发者可通过该功能，检索某一行政区划内（目前最细到城市级别）的地点信息。圆形区域检索：开发者可设置圆心和半径，检索圆形区域内的地点信息（常用于周边检索场景）。矩形区域检索：开发者可设置检索区域左下角和右上角坐标，检索坐标对应矩形内的地点信息（常用于手机或PC端地图视野内检索）地点详情检索：不同于以上三种检索功能。地点详情检索针对指定POI，检索其相关的详情信息。开发者可以通过三种区域检索（或其他服务）功能，获取POI id。使用“地点详情检索”功能，传入id，即可检索POI详情信息，如评分、营业时间等（不同类型POI对应不同类别详情数据）。常用的方式主要是第一种和第二种，今天对这两种方式都介绍一下。行政区划区域检索上次说了，API的调用方式是通过编辑好的URL，请求服务器然后返回所需要的的数据，数据是JSON或者XML类型的（别问我什么是JSON）。具体的说明大家去官网看吧balablaba的……这里我就不在BB了，直接贴上一个编辑好的URL：http://api.map.baidu.com/place/v2/search?query=超市&region=武汉市&output=json&ak=申请的AK&scope=1&page_size=20&page_num=0上面URL中，绿色标出的是需要填写的参数。各个参数的说明如下：query检索关键字。行政区划区域检索不支持多关键字检索。如果需要按POI分类进行检索，请将分类通过query参数进行设置，如query=美食。region检索行政区划区域（增加区域内数据召回权重，如需严格限制召回数据在区域内，请搭配使用city_limit参数），可输入行政区划名或对应cityCode。outpu出格式为json或者xml。ak开发者的访问密钥，必填项。v2之前该属性为key。scope检索结果详细程度。取值为1 或空，则返回基本信息；取值为2，返回检索POI详细信息。page_size单次召回POI数量，默认为10条记录，最大返回20条。多关键字检索时，返回的记录数为关键字个数*page_size。page_num分页页码，默认为0,0代表第一页，1代表第二页，以此类推。常与page_size搭配使用。关于其他可选参数更多详细信息请戳：http://lbsyun.baidu.com/index.php?title=webapi/guide/webservice-placeapi值得注意的是，page_size=20&page_num=0表示每个URL页面返回的POI数量为20个，这个是第0个页面，因为在程序中，一般都是从0开始的。好了，请求讲完了，接下来放Python代码： #coding: utf-8 import requests import json import time import csv import codecs """ 查询关键字： """ FileKey = 'preclass' KeyWord = u"超市" def getBaiduApiAk(): """ 获取配置文件中百度apikey: { "baiduak":"xx"} :return: str """ return "填写你申请的AK" def requestBaiduApi(keyWords, baiduAk, fileKey): today = time.strftime("%Y-%m-%d") pageNum = 0 count = 0 logfile = open("./" + fileKey + "-" + today + ".log", 'a+', encoding='utf-8') file = open("./" + fileKey + "-" + today + ".txt", 'a+', encoding='utf-8') file_csv = open('shops_data_青山区.csv', 'w+', encoding='utf-8') # 追加 writer = csv.writer(file_csv) writer.writerow(["no","area","name","lat","lng"]) # print('-------------') # print(index) while True: try: URL = "http://api.map.baidu.com/place/v2/search?query=" + keyWords + \ "&region=" + "武汉市青山区" + \ "&output=json" + \ "&ak=" + baiduAk + \ "&scope=1" + \ "&page_size=20" + \ "&page_num=" + str(pageNum) # print(pageNum) print(URL) resp = requests.get(URL) res = json.loads(resp.text) # print(resp.text.strip()) if len(res['results']) == 0: logfile.writelines(time.strftime("%Y%m%d%H%M%S") + " stop " + " " + str(pageNum) + '\n') break else: for r in res['results']: # print(r) count += 1 city_area = r['city']+r['area'] shop_name = r['name'] shop_lat = str(r['location']['lat']) shop_lng = str(r['location']['lng']) writer.writerow([str(count),city_area, shop_name, shop_lat, shop_lng]) # file.writelines(str(r).strip() + '\n') # print(r['city']+r['area']+" "+r['name']+" "+str(r['location']['lat']) + " " + str(r['location']['lng'])) pageNum += 1 time.sleep(1) except: print("except") logfile.writelines(time.strftime("%Y%m%d%H%M%S") + " except " + " " + str(pageNum) + '\n') break def main(): baiduAk = getBaiduApiAk() requestBaiduApi(keyWords=KeyWord, baiduAk=baiduAk, fileKey=FileKey) if __name__ == '__main__': main()（代码于2020.1.18测试无误）代码的思路也相当简单，首先是构造URL，然后请求返回JSON格式的数据，Python处理后写入CSV文件中。获取的数据详情如下所示，有需要的同学可根据说明修改相应的参数获取相应的数据：值得注意的是，在实际请求中，百度API限制了检索只能返回20个URL页面。这就意味着我们一个区域最多只能检索20*20=400个POI点。实际需求中往往不止400个点的。但人民的智慧是无穷的，我们接下来介绍第二种方式解决上面400个点的弊端。矩形区域检索所谓矩形区域检索，就是给定一个矩形范围的经纬度坐标（实际上两点即可定位一个矩形，左下点和右上点），然后在该矩形范围内进行兴趣点的检索。而矩形范围经纬度坐标的确定可以利用之前介绍的坐标拾取系统进行拾取。例如下图在武汉市（武汉加油！）拾取一个蓝色框的区域，把左下角的经纬度和右上角的经纬度记录下来即可，这样一个范围就做好啦。例如我们拾取了一个矩形：左下点的经纬度为：114.2540523, 30.471019右上点的经纬度为：114.2687126, 30.4877379现在利用矩形区域检索的URL如下：http://api.map.baidu.com/place/v2/search?query=超市&bounds=30.471019,114.2540523,30.4877379,114.2687126&output=json&ak=申请的AK&scope=1&page_size=20&page_num=0 参数无太大变化，就是region变成了bounds，并且指出了矩形区域的边界经纬度（左下点和右上点）。注意绿色处要填上你自己的AK。 好了，现在检查一下URL编辑是否正确，复制到浏览器回车一下看看： OK，大功告成。好了，现在我们来解决400个点限制的问题。不知道聪明的你们想到了没有。没错，就是切割区域。既然百度限制了每个区域检索最多只能返回400个点，那么可以通过矩形检索的方式，将一个大矩形切割成很多小矩形，依次在每个小矩形内进行检索，最后将所有小矩形的结果加起来就有很多很多个点啦。怎样，是不是很聪明呢！例如将一个大区域分割成1234号区域分别检索，假如每个区域都返回400个点，那么总共就能获取4X400=1600个点了。而如何分割，则不必手动拾取点进行划分，可以利用程序来计算嘛！好了，下面给出一份分割区域的Python代码： #coding: utf-8 import requests import json import time import csv """ 查询关键字： """ FileKey = 'preclass' KeyWord = u"便利店" """ 关注区域的左下角和右上角百度地图坐标(经纬度） """ BigRect = { 'left': { 'x': 114.239392, 'y': 30.471019 }, 'right': { 'x': 114.385995, 'y': 30.638208 } } """ 定义细分窗口的数量，横向X * 纵向Y """ WindowSize = { 'xNum': 10.0, 'yNum': 10.0 } """ 获取AK :return: str """ def getBaiduApiAk(): return "申请的AK" def getSmallRect(bigRect, windowSize, windowIndex): """ 获取小矩形的左上角和右下角坐标字符串（百度坐标系） :param bigRect: 关注区域坐标信息 :param windowSize: 细分窗口数量信息 :param windowIndex: Z型扫描的小矩形索引号 :return: lat,lng,lat,lng """ offset_x = (bigRect['right']['x'] - bigRect['left']['x'])/windowSize['xNum'] offset_y = (bigRect['right']['y'] - bigRect['left']['y'])/windowSize['yNum'] left_x = bigRect['left']['x'] + offset_x * (windowIndex % windowSize['xNum']) left_y = bigRect['left']['y'] + offset_y * (windowIndex // windowSize['yNum']) right_x = (left_x + offset_x) right_y = (left_y + offset_y) return str(left_y) + ',' + str(left_x) + ',' + str(right_y) + ',' + str(right_x) def requestBaiduApi(keyWords, smallRect, baiduAk, index, fileKey, count): today = time.strftime("%Y-%m-%d") pageNum = 0 logfile = open("./" + fileKey + "-" + today + ".log", 'a+', encoding='utf-8') file_csv = open('testdata.csv', 'w+', encoding='utf-8',newline='') # 追加 writer = csv.writer(file_csv) writer.writerow(["no","area","name","lat","lng"]) # print('-------------') # print(index) while True: try: URL = "http://api.map.baidu.com/place/v2/search?query=" + keyWords + \ "&bounds=" + smallRect + \ "&output=json" + \ "&ak=" + baiduAk + \ "&scope=1" + \ "&page_size=20" + \ "&page_num=" + str(pageNum) print(pageNum) print(URL) resp = requests.get(URL) res = json.loads(resp.text) # print(resp.text.strip()) if len(res['results']) == 0: logfile.writelines(time.strftime("%Y%m%d%H%M%S") + " stop " + str(index) + " " + smallRect + " " + str(pageNum) + '\n') break else: for r in res['results']: # print(r) count += 1 city_area = r['city'] + r['area'] shop_name = r['name'] shop_lat = str(r['location']['lat']) shop_lng = str(r['location']['lng']) writer.writerow([str(count), city_area, shop_name, shop_lat, shop_lng]) pageNum += 1 time.sleep(1) except: print("except") logfile.writelines(time.strftime("%Y%m%d%H%M%S") + " except " + str(index) + " " + smallRect + " " + str(pageNum) + '\n') break return count def main(): baiduAk = getBaiduApiAk() count = 0 for index in range(int(WindowSize['xNum'] * WindowSize['yNum'])): smallRect = getSmallRect(BigRect, WindowSize, index) count = requestBaiduApi(keyWords=KeyWord, smallRect=smallRect, baiduAk=baiduAk, index=index, fileKey=FileKey,count= count) time.sleep(1) print(str(count)) if __name__ == '__main__': main() （代码于2020.1.18测试无误）读者只需要简单修改代码中的：查询关键字关注区域的左下角和右上角百度地图坐标(经纬度）定义细分窗口的数量，横向X * 纵向Y获取AK这几处的相关信息即可使用，生成的数据如下所示：怎样，是不是很简单呢！至此，两种方式已经介绍完毕。当然，获取经纬度信息只是我们的第一步操作，后续的过程我们将向大家展示如何根据经纬度信息获取两点之间的真实距离。希望这次的疫情尽快过去，大家都相安无事！小编还要回去上学吃热干面呢！武汉加油！
-
发表了文章 2022-04-22
干货 | 10分钟教你用Python获取百度地图各点的经纬度信息
Python确实是个好东西，可以用来解决很多数据上的烦恼。结合现在各个平台提供的API，可以用Python做很多有用的需求哦~需求分析之前写论文的时候，就有这个需求了。就是抓取百度地图上某些特定的点的信息，生成测试算例去做算法后期的实验。比如下面地图：现在需要爬取地图上搜索出来的“超市”这些点的相关信息，主要包括经纬度、地点名称啊等等。首先，最笨的办法当然是先去百度地图坐标拾取系统查，然后在一个一个复制黏贴到文档上：这种办法费时费力，不符合我们的社会主义核心价值观，而且好像一次只能好到150个点（不知道怎样才能获取更多点，知道的小伙伴可以告知一下），但我们需求的点肯定不止这么少的：所以，得想想办法，能不能用一些自动化脚本，自动爬取数据保存成所需要的格式呢？百度地图POI然后百度了一下，偶然了解到了百度地图POI数据这个东西。什么是POI呢？POI是一切可以抽象为空间点的现实世界的实体，比如餐馆、酒店、商城等，POI数据具有空间坐标和各种属性，是各种地图查询软件的基础数据之一。百度地图作为国内顶尖的地图服务提供商，含有丰富的POI数据，那要如何快速获取百度地图POI兴趣点数据呢？——当然要通过Python+爬虫来完成此任务啦~~POI数据获取的关键在于构造出合适的url，访问该url便能请求到相应的POI数据。前期准备在开始之前，我们需要做一些准备工作，申请一个账号和密钥，才能调用百度地图的API进而获取所需的数据。首先要登陆百度地图开放平台http://lbsyun.baidu.com/，完成注册。这个平台是百度地图为开发者提供接口用的，有很多其他的功能，这里只讲POI爬取相关。注册登录后，在右上角进入控制台：然后找到左边应用管理下的我的应用，创建一个应用：然后，输入应用名称，应用类型选择服务端，把地点检索给勾选上。参考文档可以看具体的API调用方法。值得注意的是，IP白名单的设置，如果想任意IP调用就写上0.0.0.0/0，避免麻烦我们选择这个。创建完成后我们会得到这样一个应用的AK，就是访问密钥：在开发文档里找到Web服务API：选择地点检索V2.0的服务文档，我们会看到使用说明：其实就是通过一个编辑好的URL，请求数据，然后服务器返回相应的信息。比如使用行政区划区域检索武汉市内的超市信息，则可以编辑：http://api.map.baidu.com/place/v2/search?query=超市&region=武汉&output=json&ak=刚刚创建的应用AK输入浏览器后回车即可得到想要的信息：怎样，是不是非常简单呢！今天先介绍到这里，后续我们还会介绍几种地点检索方式以及注意的事项等。也会介绍如何根据获取的经纬度信息爬取各点之间的真实距离以及行车时间等信息。大家可以小小期待一下哦~
-
发表了文章 2022-04-22
使用这几款插件，能让你在GitHub看代码的效率翻倍
想必在GitHub上看代码交友等已经成为各大猿友们的日常。想起小编，每每在GitHub上看代码时，总感觉没有直接在IDE上看的方便。但又不想看一个代码就连带git clone到本地，再导入ide再看吧。。。所以今天小编给大家介绍一些好用的Chrome浏览器插件，将GitHub打造成一个方便的看代码神器。（好久没写文字，现在都不会表达了。）octotree：生成仓库目录这可能是我用得最多的一款插件了，大家有没有遇到过这种情况。每次点击一个文件后，整个文件列表就会被隐藏，想查看其它文件只能回退后再次进入。别提有多蛋疼了……而这款插件就完美解决了这个问题，安装插件后，它在 GitHub 页面的左侧添加了一个树目录，显示当前项目的整个文件夹结构，你可以点击浏览每个文件。GitZip 插件：下载仓库部分文件有时候看上了一个代码文件，又不想把整个项目给搞下来，用这个就对了。只需定位到某个项目子文件夹或者文件上面，在空白区域右键点击download [] as。别提有多好使了。sourcegraph：让github 具备IDE的功能可以支持快捷键、语义分析、代码搜索、跳转，甚至能跳转到SDK或framework的源码文件中。不过存在中文时有可能乱码……今天介绍的插件就这几个，其实已经够用了。小伙伴们花点时间装一装，平时看代码效率翻几倍，何乐而不为呢？
-
发表了文章 2022-04-22
干货 | 10分钟带你掌握branch and price（分支定价）算法超详细原理解析
分支定界算法从入门到跑路放弃1前言相信大家对branch and price的神秘之处也非常好奇了。今天我们一起来揭秘该算法原理过程。不过，在此之前，请大家确保自己的branch and bound和column generation的知识务必过关，而且是非常熟悉的那种。因为branch and price算法就是branch and bound和column generation的结合体。2应用背景branch and price算法就是branch and bound和column generation的结合体。具体是怎么结合的呢？先看一张BP的算法流程图，相信大家会清晰很多:3具体流程我们知道branch and bound求解整数规划的过程，如果不知道看看下面这张图回顾一下：在该过程中，定界的操作是通过求解当前问题的线性松弛(LP relaxation)得到的。对于一个变量很多的大规模整数规划问题而言，其线性松弛(LP relaxation)变量无疑也是非常多的。那么，这时候，我们上节课介绍的column generation就可以出马了。但在每一个节点中，并不需要每一次都完完整整调用一次column generation，重新构建一次RMP再求解。分子以后子节点的RMP可以直接将父节点的RMP挪过来，只不过由于加了分支约束，此时RMP需要重新添加column，再次求解以便得到最优。而子节点的RMP重新添加column，再次求解的过程就是节点的bound操作了。那么，将以上的元素综合起来，就形成了我们的branch and price算法。
-
发表了文章 2022-04-21
干货 | 10分钟教你用branch and bound（分支定界）算法求解TSP旅行商问题
前言00前面我们讲了branch and bound算法的原理以及在整数规划模型上的应用代码。但代码都局限于整数规划模型和优化求解器。我们也说了，branch and bound算法是一个比较通用的算法，可以脱离求解器去求解很多特定的问题的。所以今天给大家带来一期用分支定界算法求解TSP问题的代码实现，完全脱离求解器，让大家看看该算法的魅力所在。本文代码下载请移步留言区。程序说明01整个程序如下所示：其中各个模块说明如下：- Timer：计时用。- TSPInstanceReader：TSPLIB标准算例读取用。- PriorityQueue：优先队列。- Node：搜索树的节点。- City：保存城市的坐标，名字等。- BranchBound_TSP：BB算法主程序。该branch and bound的搜索树是以优先队列的搜索方式遍历的，结合上期所讲的内容，也可谓是把三种搜索方式的例子都给大家讲了一遍了。branch and bound过程02在此之前，先给大家讲讲最重要的一个点，搜索树的节点定义，节点定义了原问题的solution和子问题的solution。Node节点定义如下：public class Node { private ArrayList<Integer> path; private double bound; private int level; public double computeLength(double[][] distanceMatrix) { // TODO Auto-generated method stub double distance = 0; for(int i=0;i<this.getPath().size()-1;i++){ distance = distance + distanceMatrix[this.getPath().get(i)][this.getPath().get(i+1)]; } return distance; }其余不重要的接口略过。如下：- path：保存该节点目前已经走过的城市序列。- bound：记录该节点目前所能达到的最低distance。- level：记录节点处于搜索树的第几层。- computeLength：记录当前城市序列的distance。可能大家还没理解节点是如何分支的，看一张图大家就懂了。我们知道TSP问题的一个solution是能用一个序列表示城市的先后访问顺序，比如现在有4座城市（1，2，3，4）：图中每个节点的数字序列就是path保存的。大家都看到了吧，其实分支就是一个穷枚举的过程。相对于穷举，分支定界算法的优越之处就在于其加入了定界过程，在分支的过程中就砍掉了某些不可能的支，减少了枚举的次数，大大提高了算法的效率。如下：分支定界算法的主过程如下： private static void solveTSP(double[][] distanceMatrix) { int totalCities = distanceMatrix.length; ArrayList<Integer> cities = new ArrayList<Integer>(); for (int i = 0; i < totalCities; i++) { cities.add(i); } ArrayList<Integer> path; double initB = initbound(totalCities, distanceMatrix); Node v = new Node(new ArrayList<>(), 0, initB, 0); queue.add(v); queueCount++; while (!queue.isEmpty()) { v = queue.remove(); if (v.getBound() < shortestDistance) { Node u = new Node(); u.setLevel(v.getLevel() + 1); for (int i = 1; i < totalCities; i++) { path = v.getPath(); if (!path.contains(i)) { u.setPath(v.getPath()); path = u.getPath(); path.add(i); u.setPath(path); if (u.getLevel() == totalCities - 2) { // put index of only vertex not in u.path at the end // of u.path for (int j = 1; j < cities.size(); j++) { if (!u.getPath().contains(j)) { ArrayList<Integer> temp = new ArrayList<>(); temp = u.getPath(); temp.add(j); u.setPath(temp); } } path = u.getPath(); path.add(0); u.setPath(path); if (u.computeLength(distanceMatrix) < shortestDistance) { shortestDistance = u.computeLength(distanceMatrix);// implement shortestPath = u.getPath(); } } else { u.setBound(computeBound(u, distanceMatrix, cities)); //u.getBound()获得的是不完整的解，如果一个不完整的解bound都大于当前最优解，那么完整的解肯定会更大，那就没法玩了。 //所以这里只要u.getBound() < shortestDistance的分支 if (u.getBound() < shortestDistance) { queue.add(u); queueCount++; } else { System.out.println("currentBest = "+shortestDistance+" cut bound >>> "+u.getBound()); } } } } } } }1. 首先initbound利用贪心的方式获得一个bound，作为初始解。2. 而后利用优先队列遍历搜索树，进行branch and bound算法。对于队列里面的任意一个节点，只有(v.getBound() < shortestDistance)条件成立我们才有分支的必要。不然将该支砍掉。3. 分支以后判断该支是否到达最底层，这样意味着我们获得了一个完整的解。那么此时就可以更新当前的最优解了。4. 如果没有到达最底层，则对该支进行定界操作。如果该支的bound也比当前最优解还要大，那么也要砍掉的，就像林志炫的单身情歌里面唱的一样：每一个单身狗都得砍头。然后讲讲定界过程，TSP问题是如何定界的呢？private static double computeBound(Node u, double[][] distanceMatrix, ArrayList<Integer> cities) { double bound = 0; ArrayList<Integer> path = u.getPath(); for (int i = 0; i < path.size() - 1; i++) { bound = bound + distanceMatrix[path.get(i)][path.get(i + 1)]; } int last = path.get(path.size() - 1); List<Integer> subPath1 = path.subList(1, path.size()); double min; //回来的 for (int i = 0; i < cities.size(); i++) { min = Integer.MAX_VALUE; if (!path.contains(cities.get(i))) { for (int j = 0; j < cities.size(); j++) { if (i != j && !subPath1.contains(cities.get(j))) { if (min > distanceMatrix[i][j]) { min = distanceMatrix[i][j]; } } } } if (min != Integer.MAX_VALUE) bound = bound + min; } //出去的 min = Integer.MAX_VALUE; for (int i = 0; i < cities.size(); i++) { if (/*cities.get(i) != last && */!path.contains(i) && min > distanceMatrix[last][i]) { min = distanceMatrix[last][i]; } } bound = bound + min; //System.out.println("bound = "+bound); return bound; }我们知道，每个节点保存的城市序列可能不是完整的解。bound的计算方式：bound = 当前节点path序列的路径距离 + 访问下一个城市的最短路径距离 + 从下一个城市到下下城市（有可能是起点）的最短路径距离。比如城市节点5个｛1，2，3，4，5｝。当前path = ｛1，2｝，那么：- 当前节点path序列的路径距离 = d12- 访问下一个城市的最短路径距离 = min (d2i), i in {3,4,5}- 从下一个城市到下下城市（有可能是起点）的最短路径距离=min (dij), i in {3,4,5} , j in {3,4,5,1}, i != j 。注意这两个是可以不相等的。运行说明03目前分支定界算法解不了大规模的TSP问题，10个节点以内吧差不多。input里面有算例，可以更改里面的DIMENSION值告诉算法需要读入几个节点。更改算例在main函数下面，改名字就行，记得加上后缀。感兴趣的同学可以该一下heap大小跑一跑，不过按照上述的分支思路，很容易爆掉的。小编出差在外没有好的电脑就不跑了。
-
发表了文章 2022-04-21
干货 | 11分钟带你全面掌握branch and bound（分支定界）算法-概念篇（下）
03 算法框架分支定界法（branch and bound）是一种求解整数规划问题的最常用算法。这种方法不但可以求解纯整数规划，还可以求解混合整数规划问题。上面用了求解整数规划的例子，这虽然有助于我们更好理解这个算法，但是针对整数规划这一特定问题的过程描述，有可能会对我们的思维带来局限性。而不能更好的理解该算法的精髓。所以小编决定，在这一节里面，将一个更通用的算法框架呈现出来，以便大家能更好的了解分支定界算法的真正精髓所在。假设我们求的是最小化问题 minimize f(x)。branch and bound的过程可以描述如下：[1]1. Using a heuristic, find a solution xh to the optimization problem. Store its value, B = f(x_h). (If no heuristic is available, set B to infinity.) B will denote the best solution found so far, and will be used as an upper bound on candidate solutions. 2. Initialize a queue to hold a partial solution with none of the variables of the problem assigned. 3. Loop until the queue is empty: 3.1. Take a node N off the queue. 3.2. If N represents a single candidate solution x and f(x) < B, then x is the best solution so far. Record it and set B ← f(x). 3.3. Else, branch on N to produce new nodes Ni. For each of these: 3.3.1. If bound(N_i) > B, do nothing; since the lower bound on this node is greater than the upper bound of the problem, it will never lead to the optimal solution, and can be discarded. 3.3.2. Else, store Ni on the queue.其实代码该过程描述也很明了了。第1步可以用启发式找一个当前最优解B出来，如果不想也可以将B设置为正无穷。对于一个最小化问题而言，肯定是子问题的lower bound不能超过当前最优解，不然超过了，该子问题就需要剪掉了。第2第3步主要是用队列取构建一个搜索树进行搜索，具体的搜索方式由queue这个数据结构决定的。前面我们讲了，B&B是围绕着一颗搜索树进行的，那么对于一棵树而言就有很多种搜索方式：Breadth-first search (BFS)：广度优先搜索，就是横向搜索，先搜索同层的节点。再一层一层往下。这种搜索可以用FIFO queue实现。Depth-first search (DFS)：深度优先搜索，就是纵向搜索，先一个分支走到底，再跳到另一个分支走到底。这种搜索可以用LIFO queue也就是栈实现。Best-First Search：最佳优先搜索，最佳优先搜索算法是一种启发式搜索算法（Heuristic Algorithm），其基于广度优先搜索算法，不同点是其依赖于估价函数对将要遍历的节点进行估价，选择代价小的节点进行遍历，直到找到目标点为止。这种搜索可以用优先队列priority queue来实现。04 伪代码描述[1]按照上述框架的过程，下面提供了一个很详细的C++伪代码： // C++-like implementation of branch and bound, // assuming the objective function f is to be minimized CombinatorialSolution branch_and_bound_solve( CombinatorialProblem problem, ObjectiveFunction objective_function /*f*/, BoundingFunction lower_bound_function /*g*/) { // Step 1 above double problem_upper_bound = std::numeric_limits<double>::infinity; // = B CombinatorialSolution heuristic_solution = heuristic_solve(problem); // x_h problem_upper_bound = objective_function(heuristic_solution); // B = f(x_h) CombinatorialSolution current_optimum = heuristic_solution; // Step 2 above queue<CandidateSolutionTree> candidate_queue; // problem-specific queue initialization candidate_queue = populate_candidates(problem); while (!candidate_queue.empty()) { // Step 3 above // Step 3.1 CandidateSolutionTree node = candidate_queue.pop(); // "node" represents N above if (node.represents_single_candidate()) { // Step 3.2 if (objective_function(node.candidate()) < problem_upper_bound) { current_optimum = node.candidate(); problem_upper_bound = objective_function(current_optimum); } // else, node is a single candidate which is not optimum } else { // Step 3.3: node represents a branch of candidate solutions // "child_branch" represents N_i above for (auto&& child_branch : node.candidate_nodes) { if (lower_bound_function(child_branch) <= problem_upper_bound) { candidate_queue.enqueue(child_branch); // Step 3.3.2 } // otherwise, g(N_i) > B so we prune the branch; step 3.3.1 } } } return current_optimum; }
-
发表了文章 2022-04-21
干货 | 10分钟带你全面掌握branch and bound（分支定界）算法-概念篇（上）
之前一直做启发式算法，最近突然对精确算法感兴趣了。但是这玩意儿说实话是真的难，刚好boss又叫我学学column generation求解VRP相关的内容。一看里面有好多知识需要重新把握，所以这段 时间就打算好好学学精确算法。届时会把学习过程记录下来，也方便大家学习！01 什么是branch and bound？1.1官方一点[1]Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.The algorithm depends on efficient estimation of the lower and upper bounds of regions/branches of the search space. If no bounds are available, the algorithm degenerates to an exhaustive search.1.2通俗一点分支定界算法始终围绕着一颗搜索树进行的，我们将原问题看作搜索树的根节点，从这里出发，分支的含义就是将大的问题分割成小的问题。大问题可以看成是搜索树的父节点，那么从大问题分割出来的小问题就是父节点的子节点了。分支的过程就是不断给树增加子节点的过程。而定界就是在分支的过程中检查子问题的上下界，如果子问题不能产生一比当前最优解还要优的解，那么砍掉这一支。直到所有子问题都不能产生一个更优的解时，算法结束。02 原理解析为了让大家更好理解分支定界的原理，这里小编举一个求解整数规划的例子来给大家演示分支定界算法的具体过程。首先，对于一个整数规划模型：因为求解的是最大化问题，我们不妨设当前的最优解BestV为-INF，表示负无穷。1) 首先从主问题分出两支子问题：通过线性松弛求得两个子问题的upper bound为Z_LP1 = 12.75，Z_LP2 = 12.2。由于Z_LP1 和Z_LP2都大于BestV=-INF，说明这两支有搞头。继续往下。2) 从节点1和节点2两个子问题再次分支，得到如下结果：子问题3已经不可行，无需再理。子问题4通过线性松弛得到最优解为10，刚好也符合原问题0的所有约束，在该支找到一个可行解，更新BestV = 10。子问题5通过线性松弛得到upper bound为11.87>当前的BestV = 10，因此子问题5还有戏，待下一次分支。而子问题6得到upper bound为9<当前的BestV = 10，那么从该支下去找到的解也不会变得更好，所以剪掉！3) 对节点5进行分支，得到：子问题7不可行，无需再理。子问题8得到一个满足原问题0所有约束的解，但是目标值为4<当前的BestV=10，所以不更新BestV，同时该支下去也不能得到更好的解了。4) 此时，所有的分支遍历都完成，我们最终找到了最优解。
-
发表了文章 2022-04-21
【CPLEX教程01】Cplex介绍，下载和安装Cplex
前言最近学习列生成算法，需要用到优化求解器。所以打算学习一下cplex这个商业求解器。当然也有其他更多的选择，这里暂时以比较容易上手和性能比较好的cplex开始吧。其实，小编也早就想学习使用这个cplex了，毕竟是个好东西。所以打算出一系列教程推出，大家可以关注我们获取后续教程的更新哦。Cplex是什么？Cplex是IBM公司开发的一款商业版的优化引擎，当然也有免费版，只不过免费版的有规模限制，不能求解规模过大的问题。Cplex专门用于求解大规模的线性规划（LP）、二次规划（QP）、带约束的二次规划（QCQP）、二阶锥规划（SOCP）等四类基本问题，以及相应的混合整数规划（MIP）问题。优势：能解决一些非常困难的行业问题；求解速度非常快；提供超线性加速功能的优势。在Cplex的加持下，使得matlab对于大规模问题，以及线性规划的效率，都得到飞跃的提升。Cplex下载和安装由于商用版太贵，现在已经能申请教育版了，功能和商用版一样。刚好学长之前申请过一个教育版的，所以这里直接给大家分享一个出来了，这个版本是无限制的，便于我们后续的学习：下载请移步留言区。直接下载下来安装即可。至于安装，非常简单，一路下一步即可。由于是一系列教程，所以小编会一步一个脚印带领大家上手，从入门到放弃的那种。不过主要是侧重于Java和C++调用cplex库，关于OPL建模语言就请读者们自行学习啦。
-
发表了文章 2022-04-21
杂谈 | 讲讲用Linux系统作为主力的感受
01 前言相信大部分小伙伴的主力系统都是Windows，不过Windows虽然大法好，有时候也不得不面临各种各样困扰。比如装个小软件，突然发现百度360等几家人整整齐齐出现在了桌面，烦人的更新经常让我们崩溃不已，上一些正常的网站还要面临各种病毒的侵扰……在桌面系统被巨婴一家独霸天下的环境下，也是没办法，毕竟lol还是要打的……不过对于小编这种不玩游戏的开发党来说，有时候脱离一下Windows，尝试一下Linux和macos等小清新，似乎也不错？下面给大家讲讲Linux的使用感受吧。02 Why Linux首先说说为什么用Linux吧，因为Linux的字体渲染看起来真的要比Windows舒服得多，这是实话。所以在Linux搞工作，就两字：舒心。当然，将Linux作为主力系统，还是需要一定的心里承受能力的。首先就是要经得起折腾，因为Linux不像Windows那般成熟稳重，当然，我指的是桌面系统。很有可能你今天花了一天功夫配置好了输入法，明天因为干了点什么，输入法就蹦了，接着系统也跟着蹦了。或者，今天更新了系统，明天打开电脑发现进不去了……这都是有可能的，所以要经得起折腾的人才能整这玩意……其次是要耐得住寂寞，Linux上的生态是很匮乏的，可能你发现了一部好看的电影，然后发现找不到一个好的磁力下载工具下载。登个QQ微信吧，折腾半天还是几年前的版本，好不容易网易云有Linux版的了，装了发现还TM的打不开……不过Linux也有很多优点，首先是病毒问题。不说百毒不侵，起码大多数时候你是不需要担心病毒的，因为大多数病毒都是Windows下的。然后Linux这种环境对于开发人员来说还是非常友好的，起码终端比Windows的cmd好多了……再者就是应用清爽、广告基本都没有，简直就是一片净土……03 Deepin Linux在这一节给大家展示一下小编目前的生产环境，至于为什么选择Deepin Linux呢？因为省事啊……经历了这么多年的风霜，小编再也不是当年那个愿意各种折腾的年轻人了，现在做事都图个方便，因为事情太多了……Deepin对于中国的用户来说确实是一个福音，也能感受到深度是真的用心在做这个系统，而且，还是免费开源的。3.1 markdown小编日常工作还是写写文章什么的，一般还是用的markdown写，Windows下还真找不出几款好用的markdown工具。不过，在Linux的vim下装几个插件，就能媲美一款markdown软件。调个透明背景，配合浏览器的预览，加上左边装个tree目录的插件，码字简直不要太舒服。至于图片，我是直接把图片上传到简书上，然后把链接黏贴过来的。3.2 文档处理当然是国产的WPS辣！Linux下的版本可比Windows的老实多了，起码不会动不动就弹小广告之类的。小编平常也就写个作业，做个表格啥的，WPS完全够用。3.3 聊天娱乐像QQ微信什么的，Deepin已经封装好了wine版本的，用起来还是非常不错的。此外还有像迅雷什么的，也有wine版本，相比Windows版本，功能可能少了点，但是整洁清爽啊：然后浏览器方面有Google 浏览器，装上油猴以后，简直就是开挂的网络神器：比如装了某脚本，屏蔽百度的推广，搜索界面一片清爽：3.4 编程方面因为小编一般用的都是java、C++、Python多，java可以用eclipse，C++和Python可以用jetbrains的全家桶，这些都是Linux原生的应用。不过话说回来，真要搞C++小编还是会转到Windows去用微软的vs，这玩意实在是太强大了，毕竟号称宇宙第一IDE。04 系统稳定性之前用Linux就是因为桌面系统太不稳定了，精彩各种崩溃，不过用了Deepin Linux以后，感觉非常稳定，目前还没有出现过崩溃的现象。然后系统占用也蛮小的：我觉得比Windows小的多了，可能是少了很多乱七八糟的软件应用吧。05 结语总之，如果不玩游戏，日常简单办公之类的，Linux已经能满足大部分人的需求。不过上Linux可不仅仅是图个清爽这么简单，还需要有一个经得住折腾以及勇于探索的心，最后，小白还是不要乱玩了，不然把电脑整废了那可就大发了。折腾，因人而异吧～不过，花点时间配置一下，既舒服了身心，又提高了生产效率，何乐不为呢？
-
发表了文章 2022-04-21
推荐几个好用到爆炸的Google Chrome插件
这年头，上网不用Google Chrome都不好意思说自己是搞技术的高富帅……咳咳。倒不是谷歌浏览器有多高大上，而是其快速轻巧，而且插件功能强大，赢得了很多用户的好评。不过，谷歌在国内被ban了，国内用户想装个插件还没法上谷歌商店装，然后上谷歌商店还得搞个科学上网……这年头装个插件真不容易。上不了商店，只能在网上找一些插件包下载下来，再离线安装了。不过现在谷歌浏览器又把离线插件的安装方式给ban了，真的是……当然，办法总是有的，现在谷歌浏览器有个bug，在开发者模式下把插件扩展名改为zip然后拖进去就能成功安装了，下面详细讲一下，顺便介绍几个好用的插件。先讲讲怎么离线安装插件首先介绍一个插件网站，扩展迷：https://extfans.com/在这里你基本上能找到所有的插件。下载下来然后安装即可。以谷歌上网助手为例：注意：下载插件时不要用谷歌浏览器下载！注意：下载插件时不要用谷歌浏览器下载！注意：下载插件时不要用谷歌浏览器下载！点击下载以后，得到谷歌上网助手.crx，将其后缀名改为zip：然后进谷歌浏览器的扩展程序那里：把右上角的开发者模式给点开：然后把改名好的插件拖进去即可：呃……装了这个以后你就可以访问谷歌商店了。不过只有12小时的免费试用时间。然后介绍几个插件：Infinity新标签页(Pro)新建标签页时，遇见美好的Chrome新标签页，挺漂亮的，逼格也蛮高的。Adblock Plus拦截广告用的，特别实用，适合爱上乱七八糟网站的同学。OctotreeGitHub的神助攻，Extension to show code tree for GitHub，看左边栏。Tampermonkey这是一个神器了……可能你根本就没听过Tampermonkey，但是如果我告诉你，使用它，你能免费看各大视频网站的VIP电影，跳过广告、能解析出百度云盘里的真实下载链接，突破限速、能去除经常访问的一些网站上的烦人的广告模块儿，你是不是就会觉得不可思议？用神器两个字来形容Tampermonkey一点也不为过。Tampermonkey 是一款免费的浏览器扩展和最为流行的用户脚本管理器。通过它，我们能运行和管理针对某网站专用的JavaScript代码，通过文档对象模型（DOM）接口对网页内容做操作（Tamper的中文意思就是篡改）。关于DOM，前端的同学可能比较了解，非程序员可以狭义的理解为网页。Tampermonkey的强大之处，在于它提供了一个平台，来供其他脚本文件执行。这里，提供一个官网推荐的脚本网站，来供大家使用：Greasy Fork ：https://greasyfork.org/zh-CN/比如装了某脚本以后，在百度网盘自动出现：
-
发表了文章 2022-04-21
10分钟教你用Python实现微信自动回复
01 前言&&效果展示相信大家都有忙碌的时候，不可能一直守在微信上及时回复消息。但微信又不能像QQ一样设置自动回复。无妨，今天，我们就来用Python实现微信的自动回复功能吧，并且把接收到的消息统一发送到文件助手里面，方便统一查看。效果如下： 02 环境准备Python版本：3.6.0系统平台：Windows 10 X64IDE：pycharm相关模块：time模块；itchat模块；以及一些Python自带的模块。 03 实现原理其实原理很简单，主要是利用itchat登录微信后，注册消息方法。itchat将根据接收到的消息类型寻找对应的已经注册的方法。如果一个消息类型没有对应的注册方法，该消息将会被舍弃。在这里我们主要注册的是文字类型的消息方法。然后判断消息来源，如果不是自己发出的消息，则将消息转发到文件助手，然后自动回复对方。代码如下：1# 自动回复 2# 封装好的装饰器，当接收到的消息是Text，即文字消息 3# 注册消息响应事件，消息类型为'Text'，即文本消息 4@itchat.msg_register('Text') 5def text_reply(msg): 6 # 当消息不是由自己发出的时候 7 if not msg['FromUserName'] == myUserName: 8 # 发送一条提示给文件助手 9 itchat.send_msg(u"[%s]收到好友@%s 的信息：%s\n" % 10 (time.strftime("%Y-%m-%d %H:%M:%S", time.localtime(msg['CreateTime'])), 11 msg['User']['NickName'], 12 msg['Text']), 'filehelper') 13 # 回复给好友 14 return '[自动回复]您好，我现在有事不在，一会再和您联系。\n已经收到您的的信息：%s\n' % (msg['Text'])转到文件助手的时候，注意把时间什么的添加上去。看上去效果更好。 04 后台登录然后就可以把我们的微信挂在后台自动回复了。注意运行的时候获取一下自己的微信名，以便用来判断消息是不是自己发出的。1if __name__ == '__main__': 2 itchat.auto_login() 3 4 # 获取自己的UserName 5 myUserName = itchat.get_friends(update=True)[0]["UserName"] 6 itchat.run()后台登录如下：好啦，是不是很简单呢？ 05 完整代码注：代码文件获取请移步留言区。1import itchat 2import time 3 4# 自动回复 5# 封装好的装饰器，当接收到的消息是Text，即文字消息 6# 注册消息响应事件，消息类型为'Text'，即文本消息 7@itchat.msg_register('Text') 8def text_reply(msg): 9 # 当消息不是由自己发出的时候 10 if not msg['FromUserName'] == myUserName: 11 # 发送一条提示给文件助手 12 itchat.send_msg(u"[%s]收到好友@%s 的信息：%s\n" % 13 (time.strftime("%Y-%m-%d %H:%M:%S", time.localtime(msg['CreateTime'])), 14 msg['User']['NickName'], 15 msg['Text']), 'filehelper') 16 # 回复给好友 17 return '[自动回复]您好，我现在有事不在，一会再和您联系。\n已经收到您的的信息：%s\n' % (msg['Text']) 18 19if __name__ == '__main__': 20 itchat.auto_login() 21 22 # 获取自己的UserName 23 myUserName = itchat.get_friends(update=True)[0]["UserName"] 24 itchat.run()
-
发表了文章 2022-04-21
10分钟教你用Python玩转微信之好友性别比例统计分析
想必，微信对于大家来说，是再熟悉不过的了。那么，大家想不想探索一下微信上的各种奥秘呢？今天，我们一起来简单分析一下微信上的好友性别比例吧~废话不多说，开始干活。结果如下：环境准备Python版本：3.6.0系统平台：Windows 10 X64IDE：pycharm相关模块：matplotlib.pyplot模块；itchat模块；以及一些Python自带的模块。好友统计代码文件下载请移步留言区。这里还是需要用到我们的itchat模块，利用这个模块登录微信，然后获取相应的信息进行统计分析。首先是登录微信，获取好友：1# 先登录 2itchat.login() 3 4# 获取好友列表 5friends = itchat.get_friends(update=True)[0:]然后是遍历获取结果，进行性别统计：1# 初始化计数器，有男有女，当然，有些人是不填的 2male = female = other = 0 3 4# 遍历这个列表，列表里第一位是自己，所以从"自己"之后开始计算 5# 1表示男性，2女性 6for i in friends[1:]: 7 sex = i["Sex"] 8 if sex == 1: 9 male += 1 10 elif sex == 2: 11 female += 1 12 else: 13 other += 1 14 15# 总数算上，好计算比例啊～ 16total = len(friends[1:])最后输出结果：1# 好了，打印结果 2print("男性好友：%.2f%%" % (float(male) / total * 100)) 3print("女性好友：%.2f%%" % (float(female) / total * 100)) 4print("其他：%.2f%%" % (float(other) / total * 100))那，这就完了吗？不！绘制统计图代码文件下载请移步留言区。为了结果好看一点，我们再下点功夫，利用matplotlib下的pyplot将统计的结果绘制成统计图，让数据变得更加直观。matplotlib是python上的一个2D绘图库，它可以在夸平台上边出很多高质量的图像。综旨就是让简单的事变得更简单，让复杂的事变得可能。我们可以用matplotlib生成 绘图、直方图、功率谱、柱状图、误差图、散点图等 。matplotlib.pyplot：提供一个类似matlab的绘图框架。有关其相关知识，这里就不过多介绍了，大家可上网自行了解一下，我们这里用到的代码也很简单，注释也说得很清楚了：1# 颜色 2colors = ['yellowgreen', 'lightskyblue', 'lightcoral'] 3# 标签 4labels = ['other', 'male', 'female'] 5# 控制让哪个块向外一点(这里选的是中间的那个男性) 6explode = (0, 0.1, 0) 7plt.pie([other, male, female], labels=labels, explode=explode, colors=colors, autopct='%1.1f%%') 8plt.show()将相关设置设置好以后，就把饼状图show出来就可以啦。完整代码代码文件下载请移步留言区。具体的完整代码如下：1import matplotlib.pyplot as plt 2import itchat 3 4# 先登录 5itchat.login() 6 7# 获取好友列表 8friends = itchat.get_friends(update=True)[0:] 9 10# 初始化计数器，有男有女，当然，有些人是不填的 11male = female = other = 0 12 13# 遍历这个列表，列表里第一位是自己，所以从"自己"之后开始计算 14# 1表示男性，2女性 15for i in friends[1:]: 16 sex = i["Sex"] 17 if sex == 1: 18 male += 1 19 elif sex == 2: 20 female += 1 21 else: 22 other += 1 23 24# 总数算上，好计算比例啊～ 25total = len(friends[1:]) 26 27# 好了，打印结果 28print("男性好友：%.2f%%" % (float(male) / total * 100)) 29print("女性好友：%.2f%%" % (float(female) / total * 100)) 30print("其他：%.2f%%" % (float(other) / total * 100)) 31 32# 颜色 33colors = ['yellowgreen', 'lightskyblue', 'lightcoral'] 34# 标签 35labels = ['other', 'male', 'female'] 36# 控制让哪个块向外一点(这里选的是中间的那个男性) 37explode = (0, 0.1, 0) 38plt.pie([other, male, female], labels=labels, explode=explode, colors=colors, autopct='%1.1f%%') 39plt.show()
-
发表了文章 2022-04-21
10分钟教你用Python打造天气机器人+关键字自动回复+定时发送
前言Hello，各位小伙伴。自上次我们介绍了Python实现天气预报的功能以后，那个小程序还有诸多不完善的地方，今天，我们再次来完善一下我们的小程序。比如我们想给机器人发“天气”等关键字，它就自动获取天气发送给我们，或者准点准时给我们发送天气预报等消息。先来看看效果注：欲下载本文代码文件，请移步留言区。后台登录效果：微信关键字回复：怎样，心动吗？废话不多说，开始干活吧。注：欲下载本文代码文件，请移步留言区。Part1关键字回复前面我们已经实现了天气的获取和发送，现在来利用itchat的几个功能，实现关键词的提取和发送相关信息吧。在这里呢，我们需要写一个函数装饰一下itchat.msg_register([TEXT])这个函数，表示收到消息以后，额外执行一些我们期望执行的操作。（不了解修饰器的同学自己再回去补一下基础）。1# 如果对方发的是文字，则我们给对方回复以下的东西 2@itchat.msg_register([TEXT]) 3def text_reply(msg): 4 match = re.search('天气',msg['Text']) 5 if match: 6 city = msg['Text'][msg['Text'].find("+")+1:] 7 weather_main(msg['FromUserName'], city)这部分操作也很简单，首先获取我们收到的文本消息，然后在里面找找看有没有我们想要的关键词，比如“天气”等，最后，将天气后面的城市给提取出来，获取必要的信息后，将发信人，城市传给上节课写好的weather_main()函数里面，实现消息发送。当然，上节课的weather_main()也要做相应修改，不过改动不大，大家看最后代码即可。注：欲下载本文代码文件，请移步留言区。Part2定时发送然后再来看看定时发送的功能吧。这个功能就比较简单了，一个sleep函数睡到底就行。主要是设置隔多长时间给想关的人发送天气预报。1def timer(n): 2 ''''' 3 每n秒执行一次 4 ''' 5 while True: 6 weather_main("要发送的人备注", "城市") # 此处为要执行的任务 7 time.sleep(n)比较简单吧。如果大家对文中所叙内容还有疑问或想要交流心得建议，欢迎移步留言区！
-
发表了文章 2022-04-21
10分钟教你用Python打造微信天气预报机器人
前言最近武汉的天气越来越恶劣了。动不动就下雨，所以，拥有一款好的天气预报工具，对于我们大学生来说，还真是挺重要的了。好了，自己动手，丰衣足食，我们来用Python打造一个天气预报的微信机器人吧。效果展示效果如下：后台登录收到天气预报消息：环境配置Python版本：3.6.0系统平台：Windows 10 X64相关模块：json模块；requests模块；itchat模块；以及一些Python自带的模块。获取天气主要原理很简单，找一个天气的API接口（这里我们使用的是http://api.map.baidu.com/telematics/v3/weather?location=%s&output=json&ak=TueGDhCvwI6fOrQnLM0qmXxY9N0OkOiQ&callback=?），使用requests发起请求，接受返回的结果，用python中内置的包json. 将json字符串转换为python的字典或列表，然后从字典中取出数据。具体可以看代码：1 city = input('请输入要查询的城市名称：') 2 3 url = 'http://api.map.baidu.com/telematics/v3/weather?location=%s&output=json&ak=TueGDhCvwI6fOrQnLM0qmXxY9N0OkOiQ&callback=?'%city 4 # 使用requests发起请求，接受返回的结果 5 rs = requests.get(url) 6 # 使用loads函数，将json字符串转换为python的字典或列表 7 rs_dict = json.loads(rs.text) 8 # 取出error 9 error_code = rs_dict['error'] 10 # 如果取出的error为0，表示数据正常，否则没有查询到结果 11 if error_code == 0: 12 # 从字典中取出数据 13 results = rs_dict['results'] 14 # 根据索引取出天气信息字典 15 info_dict = results[0] 16 # 根据字典的key，取出城市名称 17 city_name = info_dict['currentCity'] 18 # 取出pm值 19 pm25 = info_dict['pm25'] 20 print('当前城市：%s pm值：%s'%(city_name,pm25)) 21 # 取出天气信息列表 22 weather_data = info_dict['weather_data'] 23 # for循环取出每一天天气的小字典 24 for weather_dict in weather_data: 25 # 取出日期，天气，风级，温度 26 date = weather_dict['date'] 27 weather = weather_dict['weather'] 28 wind = weather_dict['wind'] 29 temperature = weather_dict['temperature']注释很明了。相信大家都能get it！发送天气预报在获取到天气预报的数据以后，接下来就是通过itchat模块把信息发送到我们的微信上面了。原理也很简单，先扫码登录我们的微信机器人，然后通过备注名获取要发送的好友，send过去就OK啦。具体看下面代码：1# nickname = input('please input your firends\' nickname : ' ) 2 # 想给谁发信息，先查找到这个朋友,name后填微信备注即可 3 # users = itchat.search_friends(name=nickname) 4 users = itchat.search_friends(name='起风了') # 使用备注名来查找实际用户名 5 # 获取好友全部信息,返回一个列表,列表内是一个字典 6 print(users) 7 # 获取`UserName`,用于发送消息 8 userName = users[0]['UserName'] 9 itchat.send(date+weather+wind+temperature, toUserName=userName)说说怎么实现每天定时预报：可以在程序加个while(True)，然后每天定时获取天气，send过去。当然，你最好有一天云主机，把程序挂在主机上面就OK。另一种实用的思路是：收取消息关键字，然后回复天气。这个给大家思考实现啦。完整代码完整代码如下：1# 天气预告 2# url 统一资源定位符 3# windows + r cmd 打开命令行工具 输入pip install requests 4# 引入 requests 5import requests 6# 引入python中内置的包json. 用来解析和生成json数据的 7import json 8import itchat 9 10 11def weather_main(): 12 city = input('请输入要查询的城市名称：') 13 14 url = 'http://api.map.baidu.com/telematics/v3/weather?location=%s&output=json&ak=TueGDhCvwI6fOrQnLM0qmXxY9N0OkOiQ&callback=?'%city 15 # 使用requests发起请求，接受返回的结果 16 rs = requests.get(url) 17 # 使用loads函数，将json字符串转换为python的字典或列表 18 rs_dict = json.loads(rs.text) 19 # 取出error 20 error_code = rs_dict['error'] 21 # 如果取出的error为0，表示数据正常，否则没有查询到结果 22 if error_code == 0: 23 # 从字典中取出数据 24 results = rs_dict['results'] 25 # 根据索引取出天气信息字典 26 info_dict = results[0] 27 # 根据字典的key，取出城市名称 28 city_name = info_dict['currentCity'] 29 # 取出pm值 30 pm25 = info_dict['pm25'] 31 print('当前城市：%s pm值：%s'%(city_name,pm25)) 32 # 取出天气信息列表 33 weather_data = info_dict['weather_data'] 34 # for循环取出每一天天气的小字典 35 for weather_dict in weather_data: 36 # 取出日期，天气，风级，温度 37 date = weather_dict['date'] 38 weather = weather_dict['weather'] 39 wind = weather_dict['wind'] 40 temperature = weather_dict['temperature'] 41 print('%s %s %s %s'%(date,weather,wind,temperature)) 42 43 # nickname = input('please input your firends\' nickname : ' ) 44 # 想给谁发信息，先查找到这个朋友,name后填微信备注即可 45 # users = itchat.search_friends(name=nickname) 46 users = itchat.search_friends(name='起风了') # 使用备注名来查找实际用户名 47 # 获取好友全部信息,返回一个列表,列表内是一个字典 48 print(users) 49 # 获取`UserName`,用于发送消息 50 userName = users[0]['UserName'] 51 itchat.send(date+weather+wind+temperature, toUserName=userName) 52 53 print('succeed') 54 55 else: 56 print('没有查询到天气信息') 57 58 59itchat.auto_login() 60weather_main()
-
发表了文章 2022-04-21
10分钟教你用Visual Studio 2017将代码上传到GitHub（一）
前言关于微软的Visual Studio系列，真可谓是宇宙最强IDE了。不过，像小编这样的菜鸟级别也用不到几个功能。今天给大家介绍一个比较实用的功能吧，把Visual Studio 2017里面写好的代码一键上传到GitHub。毕竟，在这个面试官一上来就要GitHub地址的年代，还不会用全球最大的同性交友网托管代码，都不好意思说自己是搞技术的了。准备工作首先确保做好以下准备工作了：1.下载安装好Visual Studio 20172.注册好一个GitHub账号3.会写helloworld。差不多就是这样。本地Git存储库和GitHub对接在打开VS2017的时候，大概会看到如下场景：首先定位到右下角，点到【团队资源管理器】。然后找到一个蓝色的【管理连接】。点击Connect to GitHub，输入账号密码。输入账号密码登陆。连接成功以后，就可以点GitHub上面的create创建仓库管理代码了。如下图，输入仓库名称和描述，设置好本地路径，点Create就可以了。小编在这里创建了一个test仓库演示。创建完成以后，GitHub和本地Git存储库会进行仓库同步，如下：现在我们大体已经搞定了。然后嘛，就是在本地的Git存储库里面写代码，然后push到我们的GitHub上面就可以了。
-
发表了文章 2022-04-21
【干货】给大家推荐一个好用的图床网站（极简图床+七牛云打造markdown利器）
markdown最近是越来越流行了，不是因为markdown有多高大上，而是它对于各大技术党来说，写文章或者写博客确确实实方便了不少。广大程序猿们不用再去关心各种格式排版问题。不过，写markdown或者博客的时候，想必各位看官都遇到过一个问题：图片往哪放。有时候喜欢网上的一个图片，把图片链接复制到文章中就可以把图片显示出来了。但是这样做，一来网站挂了，文章的图片也随之挂了。而来嘛，想放点自己的图片就无从下手了。也有一些markdown软件支持上传本地图片，但这样的软件一般也是收费的……今天介绍两个网站，解决大家这个问题吧。先介绍下图床，简单说图床就是一个在网络上存储图片的地方，目的是为了节省本地服务器空间，加快图片打开速度。个人用户一般不会使用，主要是个人博客和小网站使用。1.七牛云注册认证后有10G永久免费空间，每月10G国内和10G国外流量，速度相当快，七牛云时国内专业CDN服务商，插件支持比较多，优先推荐大家选择这个。注册成功后，在个人中心，密钥管理那里找到AK和SK，记下来，下面的极简图床要用。2.极简图床极简图床是一个免费图片上传的网站，主要提供图片上传和管理界面，需要用户自己设置微博、七牛云或者阿里云OSS信息。点击右上角的设置按钮图标，把上面七牛云的AK和SK填写进去。这样就可以在极简图床里上传和管理自己的照片到七牛云的空间了。对于需要图片外链的小伙伴来说，确实是个挺方便的功能。比如下面：
2022年04月
-
04.23 18:29:11
发表了文章
2022-04-23 18:29:11
开源线性规划求解器（Linear Programming solver）LP_Solve和CLP的PK
开源线性规划求解器（Linear Programming solver）LP_Solve和CLP的PK
-
04.23 18:26:20发表了文章
2022-04-23 18:26:20
深度学习结合树搜索求解集装箱预翻箱问题
深度学习结合树搜索求解集装箱预翻箱问题
-
04.23 18:24:28发表了文章
2022-04-23 18:24:28
基于学习的方法决定在哪些分支节点上运行heuristic算法
基于学习的方法决定在哪些分支节点上运行heuristic算法
-
04.23 18:23:01发表了文章
2022-04-23 18:23:01
科研狗文献管理阅读必备的两大神器
科研狗文献管理阅读必备的两大神器
-
04.23 18:20:52发表了文章
2022-04-23 18:20:52
机器学习在组合优化中的应用（上）
机器学习在组合优化中的应用（上）
-
04.23 18:19:03发表了文章
2022-04-23 18:19:03
模拟退火(SA)算法求解Max-Minsum Dispersion Problem（附代码及详细注释）
模拟退火(SA)算法求解Max-Minsum Dispersion Problem（附代码及详细注释）
-
04.23 18:14:44发表了文章
2022-04-23 18:14:44
来聊聊最短路问题中的label-setting算法
来聊聊最短路问题中的label-setting算法
-
04.23 18:13:05发表了文章
2022-04-23 18:13:05
写代码一天，debug一年？
写代码一天，debug一年？
-
04.23 18:11:31发表了文章
2022-04-23 18:11:31
来打造一个舒适的Latex环境吧~
来打造一个舒适的Latex环境吧~
-
04.23 18:08:11发表了文章
2022-04-23 18:08:11
手把手教你用CPLEX求解一个数学模型（Java版）
手把手教你用CPLEX求解一个数学模型（Java版）
-
04.23 18:04:51发表了文章
2022-04-23 18:04:51
CPLEX出现'q1' is not convex？
CPLEX出现'q1' is not convex？
-
04.23 18:01:12发表了文章
2022-04-23 18:01:12
好码分享：开源算法框架Open Tabu Search求解VRPTW的JAVA代码
好码分享：开源算法框架Open Tabu Search求解VRPTW的JAVA代码
-
04.23 17:58:14发表了文章
2022-04-23 17:58:14
branch and price求解VRPTW问题代码详解
branch and price求解VRPTW问题代码详解
-
04.23 17:32:48发表了文章
2022-04-23 17:32:48
基于branch and bound插入的large neighborhood search
基于branch and bound插入的large neighborhood search
-
04.23 17:20:46发表了文章
2022-04-23 17:20:46
Ubuntu Server搭建Hyperledger Fabric 2.1学习环境
Ubuntu Server搭建Hyperledger Fabric 2.1学习环境
-
04.23 17:13:34发表了文章
2022-04-23 17:13:34
如何实现一个高效的启发式算法？（VRPTW篇）
如何实现一个高效的启发式算法？（VRPTW篇）
-
04.23 17:11:27发表了文章
2022-04-23 17:11:27
如何实现一个高效的启发式算法？
如何实现一个高效的启发式算法？
-
04.23 17:05:59发表了文章
2022-04-23 17:05:59
混合算法(GA+TS)求解作业车间调度问题代码解读+完整JAVA代码
混合算法(GA+TS)求解作业车间调度问题代码解读+完整JAVA代码
-
04.23 17:03:33发表了文章
2022-04-23 17:03:33
混合算法(GA+TS)求解作业车间调度问题(JSP)-禁忌搜索部分
混合算法(GA+TS)求解作业车间调度问题(JSP)-禁忌搜索部分
-
04.23 17:01:23发表了文章
2022-04-23 17:01:23
种群进化+邻域搜索的混合算法(GA+TS)求解作业车间调度问题(JSP)-算法介绍
种群进化+邻域搜索的混合算法(GA+TS)求解作业车间调度问题(JSP)-算法介绍
-
04.23 16:56:45发表了文章
2022-04-23 16:56:45
帝国竞争算法(imperialist competitive algorithm, ICA )详解+Java代码
帝国竞争算法(imperialist competitive algorithm, ICA )详解+Java代码
-
04.23 16:43:32发表了文章
2022-04-23 16:43:32
10分钟教你用Python爬取Baidu文库全格式内容
10分钟教你用Python爬取Baidu文库全格式内容
-
04.23 16:35:38发表了文章
2022-04-23 16:35:38
使用Picgo+GitHub+ jsDelivr搭建CDN加速免费图床
使用Picgo+GitHub+ jsDelivr搭建CDN加速免费图床
-
04.23 16:28:38发表了文章
2022-04-23 16:28:38
令人头疼的代码命名规范……
令人头疼的代码命名规范……
-
04.23 16:26:32发表了文章
2022-04-23 16:26:32
如何优雅的敲公式？
如何优雅的敲公式？
-
04.23 16:20:48发表了文章
2022-04-23 16:20:48
当代码无法运行的时候，我在想什么？
当代码无法运行的时候，我在想什么？
-
04.23 16:18:34发表了文章
2022-04-23 16:18:34
番茄路径优化系统介绍
番茄路径优化系统介绍
-
04.23 16:11:37发表了文章
2022-04-23 16:11:37
10分钟教你用Python打造学生成绩管理系统
10分钟教你用Python打造学生成绩管理系统
-
04.23 16:00:04发表了文章
2022-04-23 16:00:04
10分钟用Python或MATLAB制作漂亮的甘特图（Gantt）
10分钟用Python或MATLAB制作漂亮的甘特图（Gantt）
-
04.23 11:21:14发表了文章
2022-04-23 11:21:14
在家期间为了从GitHub上下点东西，我太难了
在家期间为了从GitHub上下点东西，我太难了
-
04.23 11:14:38发表了文章
2022-04-23 11:14:38
Python中利用Matplotlib绘制多图并合并展示
Python中利用Matplotlib绘制多图并合并展示
-
04.23 11:12:24发表了文章
2022-04-23 11:12:24
数据结构之图论（续）
数据结构之图论（续）
-
04.23 11:07:17发表了文章
2022-04-23 11:07:17
干货 | Python人工智能在贪吃蛇游戏中的应用探索（上）（三）
干货 | Python人工智能在贪吃蛇游戏中的应用探索（上）（三）
-
04.23 11:05:17发表了文章
2022-04-23 11:05:17
干货 | Python人工智能在贪吃蛇游戏中的应用探索（上）（二）
干货 | Python人工智能在贪吃蛇游戏中的应用探索（上）（二）
-
04.23 11:01:39发表了文章
2022-04-23 11:01:39
干货 | Python人工智能在贪吃蛇游戏中的应用探索（上）（一）
干货 | Python人工智能在贪吃蛇游戏中的应用探索（上）（一）
-
04.23 10:56:53发表了文章
2022-04-23 10:56:53
干货 | 数据结构之图论基础
干货 | 数据结构之图论基础
-
04.23 10:46:36发表了文章
2022-04-23 10:46:36
干货 | Python爬虫实战（中）：数据可视化-教你做出漂亮的图表
干货 | Python爬虫实战（中）：数据可视化-教你做出漂亮的图表
-
04.23 10:39:18发表了文章
2022-04-23 10:39:18
干货 | Python爬虫实战：两点间的真实行车时间与路况分析（二）
干货 | Python爬虫实战：两点间的真实行车时间与路况分析（二）
-
04.23 10:28:12发表了文章
2022-04-23 10:28:12
干货 | Python爬虫实战：两点间的真实行车时间与路况分析（一）
干货 | Python爬虫实战：两点间的真实行车时间与路况分析（一）
-
04.23 10:22:07发表了文章
2022-04-23 10:22:07
干货 | 模拟退火、禁忌搜索、迭代局部搜索求解TSP问题Python代码分享
干货 | 模拟退火、禁忌搜索、迭代局部搜索求解TSP问题Python代码分享
-
04.23 10:16:02发表了文章
2022-04-23 10:16:02
干货 | 自适应大邻域搜索（ALNS）和禁忌搜索（TS）实验对比附代码
干货 | 自适应大邻域搜索（ALNS）和禁忌搜索（TS）实验对比附代码
-
04.23 10:12:09发表了文章
2022-04-23 10:12:09
干货 | 数据结构与算法 - 什么是算法
干货 | 数据结构与算法 - 什么是算法
-
04.23 10:04:21发表了文章
2022-04-23 10:04:21
干货 | 数据结构的基本概念介绍
干货 | 数据结构的基本概念介绍
-
04.23 09:54:52发表了文章
2022-04-23 09:54:52
干货 | Tabu Search求解作业车间调度问题(Job Shop Scheduling)-附Java代码
干货 | Tabu Search求解作业车间调度问题(Job Shop Scheduling)-附Java代码
-
04.23 09:48:42发表了文章
2022-04-23 09:48:42
分享 | C#编写的电影售票系统（附源码+数据库）
分享 | C#编写的电影售票系统（附源码+数据库）
-
04.23 09:40:48发表了文章
2022-04-23 09:40:48
干货|蚁群算法求解带时间窗的车辆路径规划问题详解（附Java代码）
干货|蚁群算法求解带时间窗的车辆路径规划问题详解（附Java代码）
-
04.23 09:36:09发表了文章
2022-04-23 09:36:09
10分钟教你Python爬虫（下）--爬虫的基本模块与简单的实战
10分钟教你Python爬虫（下）--爬虫的基本模块与简单的实战
-
04.22 16:29:58发表了文章
2022-04-22 16:29:58
10分钟教你Python爬虫（上）-- HTML和爬虫基础
10分钟教你Python爬虫（上）-- HTML和爬虫基础
-
04.22 16:23:36发表了文章
2022-04-22 16:23:36
作业车间调度JSP与遗传算法GA及其Python/Java/C++实现
作业车间调度JSP与遗传算法GA及其Python/Java/C++实现
-
发表了文章
2022-04-23
开源线性规划求解器（Linear Programming solver）LP_Solve和CLP的PK
-
发表了文章
2022-04-23
深度学习结合树搜索求解集装箱预翻箱问题
-
发表了文章
2022-04-23
基于学习的方法决定在哪些分支节点上运行heuristic算法
-
发表了文章
2022-04-23
科研狗文献管理阅读必备的两大神器
-
发表了文章
2022-04-23
机器学习在组合优化中的应用（上）
-
发表了文章
2022-04-23
模拟退火(SA)算法求解Max-Minsum Dispersion Problem（附代码及详细注释）
-
发表了文章
2022-04-23
来聊聊最短路问题中的label-setting算法
-
发表了文章
2022-04-23
写代码一天，debug一年？
-
发表了文章
2022-04-23
来打造一个舒适的Latex环境吧~
-
发表了文章
2022-04-23
手把手教你用CPLEX求解一个数学模型（Java版）
-
发表了文章
2022-04-23
CPLEX出现'q1' is not convex？
-
发表了文章
2022-04-23
好码分享：开源算法框架Open Tabu Search求解VRPTW的JAVA代码
-
发表了文章
2022-04-23
branch and price求解VRPTW问题代码详解
-
发表了文章
2022-04-23
基于branch and bound插入的large neighborhood search
-
发表了文章
2022-04-23
Ubuntu Server搭建Hyperledger Fabric 2.1学习环境
-
发表了文章
2022-04-23
如何实现一个高效的启发式算法？（VRPTW篇）
-
发表了文章
2022-04-23
如何实现一个高效的启发式算法？
-
发表了文章
2022-04-23
混合算法(GA+TS)求解作业车间调度问题代码解读+完整JAVA代码
-
发表了文章
2022-04-23
混合算法(GA+TS)求解作业车间调度问题(JSP)-禁忌搜索部分
-
发表了文章
2022-04-23
种群进化+邻域搜索的混合算法(GA+TS)求解作业车间调度问题(JSP)-算法介绍
