技术领域technical field
本发明涉及管件加工领域，特别是涉及一种基于遗传算法的多规格一维套料方法及装置。The invention relates to the field of pipe fitting processing, in particular to a genetic algorithm-based multi-standard one-dimensional nesting method and device.
背景技术Background technique
套料是机械加工行业、船舶制造等行业常用的方法，是指下料的时候，为了减少对原料的浪费，在原料上安排了较大或较长的下料后，再分配一些较小的下料，从而在有限的原料上尽可能分配多的下料进行生产，提高对原料的利用率，降低成本，节约资源。Nesting is a commonly used method in the machinery processing industry, shipbuilding and other industries. It means that when cutting materials, in order to reduce the waste of raw materials, after arranging larger or longer cutting materials on the raw materials, then distribute some smaller ones. Cutting, so as to allocate as much cutting as possible on the limited raw materials for production, improve the utilization rate of raw materials, reduce costs and save resources.
目前在实际生产过程中，套料方案由工人自行计算得到。工人根据经验和简单的对比，尽量保证单根原料管材产生的废料最少。这相当于一种“贪心”策略，在多根原料下料时，分别保证每根原料都浪费最少来保证全部原料浪费最少，即以局部最优解逼近全局最优解。这种人工“贪心”的计算方法并不能保证整体的套料方案是最优的，即无法证明局部最优解能收敛到全局最优解。At present, in the actual production process, the nesting scheme is calculated by the workers themselves. Based on experience and simple comparison, workers try to ensure that the waste produced by a single raw material pipe is the least. This is equivalent to a "greedy" strategy. When cutting multiple raw materials, each raw material is guaranteed to be wasted at least to ensure the least waste of all raw materials, that is, the local optimal solution is close to the global optimal solution. This artificial "greedy" calculation method cannot guarantee that the overall nesting scheme is optimal, that is, it cannot prove that the local optimal solution can converge to the global optimal solution.
因此，如何从整体角度考虑套料方法，保证在一套原料的分配方案中尽可能达到全局最优解，是本领域技术人员需要解决的技术问题。Therefore, how to consider the nesting method from an overall point of view to ensure that a global optimal solution is achieved as much as possible in a set of raw material allocation schemes is a technical problem to be solved by those skilled in the art.
发明内容Contents of the invention
本发明的目的是提供一种基于遗传算法的多规格一维套料方法及装置，用于从整体角度考虑套料方法，保证在一套原料的分配方案中尽可能达到全局最优解。The object of the present invention is to provide a multi-standard one-dimensional nesting method and device based on a genetic algorithm, which is used to consider the nesting method from an overall point of view, and ensure that the global optimal solution is achieved as much as possible in a set of raw material allocation schemes.
为解决上述技术问题，本发明提供一种基于遗传算法的多规格一维套料方法，包括：In order to solve the above-mentioned technical problems, the present invention provides a multi-standard one-dimensional nesting method based on genetic algorithm, including:
以原料为个体，以下料为基因，在各所述基因中随机选择基因对各所述个体进行编码，得到各所述个体的基因编码，以获得所述基因编码的各所述个体作为初始种群；Taking the raw material as an individual, and the following material as a gene, randomly select a gene from each of the genes to encode each of the individuals, obtain the gene code of each of the individuals, and obtain each of the individuals encoded by the genes as the initial population ;
以所述初始种群作为父代种群，对所述父代种群应用交叉运算或变异运算中至少一种运算以及选择运算，直至获得整体适应度满足预设条件的子代种群；Using the initial population as a parent population, applying at least one of a crossover operation or a mutation operation and a selection operation to the parent population until a child population whose overall fitness meets a preset condition is obtained;
其中，所述原料为未经切割的管材；所述下料为需要切割产生的管材；所述整体适应度为一代种群中所有个体的个体适应度之和；所述个体适应度为个体利用率；所述个体利用率为一个所述原料上分配的所有下料的长度之和占所述原料的长度的比值。Wherein, the raw material is an uncut pipe; the cutting material is a pipe that needs to be cut; the overall fitness is the sum of the individual fitness of all individuals in the first generation population; the individual fitness is the individual utilization rate ; The individual utilization rate is the ratio of the sum of the lengths of all cut materials allocated on the raw material to the length of the raw material.
可选地，所述在各所述基因中随机选择基因对各所述个体进行编码，得到各所述个体的基因编码，具体包括：Optionally, the random selection of genes in each of the genes to encode each of the individuals, to obtain the gene encoding of each of the individuals, specifically includes:
计算个体的预设基因编码长度；所述预设基因编码长度为一个所述个体上能够携带的基因数量的最大值；Calculating the preset gene encoding length of an individual; the preset gene encoding length is the maximum value of the number of genes that can be carried by an individual;
随机且不重复地选择多组基因，直至生成的基因编码的数量等于所述个体的数量；Select sets of genes randomly and without repetition until the number of gene codes generated is equal to the number of individuals;
当所述基因编码的长度大于所述预设基因编码长度时，舍弃所述基因编码；When the length of the gene code is greater than the preset length of the gene code, the gene code is discarded;
当所述基因编码的长度小于所述预设基因编码长度时，在所述基因编码中随机插入空格以使所述基因编码的长度等于所述预设基因编码长度。When the length of the gene code is less than the preset length of the gene code, randomly insert spaces into the gene code to make the length of the gene code equal to the preset length of the gene code.
可选地，还包括：Optionally, also include:
当所述个体携带的基因所代表的下料的长度之和大于所述个体所代表的原料的长度时，重新对所述个体进行编码。When the sum of the lengths of the trimmings represented by the genes carried by the individual is greater than the length of the raw material represented by the individual, the individual is re-encoded.
可选地，所述对所述父代种群进行所述交叉运算，具体为：Optionally, the performing the cross operation on the parent population is specifically:
对所述父代种群中的父代个体按个体适应度非递增的方式进行排序，对相邻的父代个体两两之间以基因为单位进行所述交叉运算。The parent individuals in the parent population are sorted in a non-increasing manner of individual fitness, and the crossover operation is performed on pairs of adjacent parent individuals in units of genes.
可选地，所述对相邻的父代个体两两之间以基因为单位进行所述交叉运算，具体包括：Optionally, performing the cross operation on a gene-by-gene basis between adjacent parent individuals, specifically includes:
选择交叉点；select the intersection;
由两个所述相邻的父代个体之间交换所述交叉点之前的基因产生两个子代个体。Two offspring individuals are generated by exchanging genes before the intersection point between the two adjacent parent individuals.
可选地，所述对所述父代种群进行所述变异运算，具体包括：Optionally, the performing the mutation operation on the parent population specifically includes:
随机选择一个基因；Randomly select a gene;
判断所述父代种群中是否包括所述基因；judging whether the gene is included in the parent population;
如果是，则返回所述随机选择一个基因的步骤；If yes, then return to the step of randomly selecting a gene;
如果否，则在所述父代种群中选择一个基因进行替换。If not, a gene is selected for replacement in the parent population.
可选地，在所述判断所述父代种群中是否包括所述基因之前，还包括：Optionally, before the judging whether the gene is included in the parent population, it also includes:
以所述父代种群中的所有基因构造平衡二叉树结构。A balanced binary tree structure is constructed with all genes in the parent population.
可选地，所述对所述父代种群进行所述选择运算，具体包括：Optionally, the performing the selection operation on the parent population specifically includes:
判断生成的子代种群的整体适应度是否大于所述父代种群的整体适应度；Judging whether the overall fitness of the generated offspring population is greater than the overall fitness of the parent population;
如果所述子代种群的整体适应度大于所述父代种群的整体适应度，则判断所述子代种群的整体适应度是否满足预设条件；如果是，则结束运算；如果否，则以所述子代种群为父代种群进行所述交叉运算或所述变异运算中的至少一种运算以及所述选择运算后，对新的父代种群和子代种群进行所述判断生成的子代种群的整体适应度是否大于所述父代种群的整体适应度的步骤；If the overall fitness of the offspring population is greater than the overall fitness of the parent population, then judge whether the overall fitness of the offspring population satisfies the preset condition; if yes, end the operation; The child population is a child population generated by performing the judgment on a new parent population and a child population after performing at least one of the cross operation or the mutation operation and the selection operation on the parent population The step of whether the overall fitness of is greater than the overall fitness of the parent population;
如果所述子代种群的整体适应度小于等于所述父代种群的整体适应度，则返回对所述父代种群进行所述交叉运算或所述变异运算中的至少一种运算以及所述选择运算的步骤。可选地，所述判断生成的子代种群的整体适应度是否大于所述父代种群的整体适应度，具体包括：If the overall fitness of the child population is less than or equal to the overall fitness of the parent population, return to performing at least one of the crossover operation or the mutation operation on the parent population and the selection operation steps. Optionally, the judging whether the overall fitness of the generated offspring population is greater than the overall fitness of the parent population specifically includes:
在所述子代种群中选择预设数量的个体，计算所述预设数量的个体的个体适应度之和得到子代部分个体适应度之和；Selecting a preset number of individuals in the offspring population, calculating the sum of the individual fitness of the preset number of individuals to obtain the sum of the individual fitness of the offspring;
在所述父代种群中选择所述预设数量的个体，计算所述预设数量的个体的个体适应度之和得到父代部分个体适应度之和；Selecting the preset number of individuals in the parent population, calculating the sum of the individual fitness of the preset number of individuals to obtain the sum of the individual fitness of the parent generation;
判断所述子代部分个体适应度之和是否大于所述父代部分个体适应度之和。It is judged whether the sum of the individual fitness of the offspring is greater than the sum of the individual fitness of the parent.
为解决上述技术问题，本发明还提供一种基于遗传算法的多规格一维套料装置，包括：In order to solve the above technical problems, the present invention also provides a genetic algorithm-based multi-standard one-dimensional nesting device, including:
存储器，用于存储指令，所述指令包括上述任意一项所述基于遗传算法的多规格一维套料的方法的步骤；The memory is used to store instructions, and the instructions include the steps of any one of the above-mentioned methods for multi-standard one-dimensional nesting based on genetic algorithms;
处理器，用于执行所述指令。a processor for executing the instructions.
本发明所提供的基于遗传算法的多规格一维套料方法，以原料作为个体，以下料作为基因，以利用率作为适应度；随机选择基因对所有个体进行编码从而形成初始种群，相当于获得了一个对所有原料的整体分配方案；再以初始种群作为父代种群，对父代种群应用交叉运算或变异运算中至少一种运算以及选择运算，直至获得整体适应度满足预设条件的子代种群，相当于从全局角度考虑整体分配方案的优劣，从而获得对于多规格原料的套料方案的全局最优解。相比于现有技术中的人工“贪心”算法，从全局角度得到了更加节约原料的方案，且无需实现给出一根原料上所有的套料方案，避免了在原料管材和下料管材规格较多、数量较大时造成的计算复杂、耗时较多的情况，节约了人力，更符合车间生产的实际需要。本发明还提供一种基于遗传算法的多规格一维套料装置，具有上述有益效果。The multi-standard one-dimensional nesting method based on genetic algorithm provided by the present invention uses raw materials as individuals, following materials as genes, and utilization rate as fitness; random selection of genes encodes all individuals to form an initial population, which is equivalent to obtaining An overall allocation scheme for all raw materials is established; then the initial population is used as the parent population, and at least one of the crossover operation or the mutation operation and the selection operation are applied to the parent population until the offspring whose overall fitness meets the preset conditions are obtained The population is equivalent to considering the advantages and disadvantages of the overall allocation scheme from a global perspective, so as to obtain the global optimal solution for the nesting scheme of multi-standard raw materials. Compared with the artificial "greedy" algorithm in the prior art, a more raw material-saving scheme is obtained from a global perspective, and there is no need to implement all the nesting schemes on a raw material, avoiding the specification of raw material pipes and blanking pipes The complex calculation and time-consuming situation caused by large quantities and large quantities saves manpower and is more in line with the actual needs of workshop production. The present invention also provides a multi-standard one-dimensional nesting device based on a genetic algorithm, which has the above beneficial effects.
附图说明Description of drawings
为了更清楚的说明本发明实施例或现有技术的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单的介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。In order to more clearly illustrate the embodiments of the present invention or the technical solutions of the prior art, the following will briefly introduce the accompanying drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only For some embodiments of the present invention, those skilled in the art can also obtain other drawings based on these drawings without creative work.
图1为本发明实施例提供的一种基于遗传算法的多规格一维套料方法的流程图；Fig. 1 is the flow chart of a kind of multi-standard one-dimensional nesting method based on genetic algorithm provided by the embodiment of the present invention;
图2为本发明实施例提供的一种在各基因中随机选择基因以对各个体进行基因编码的具体实施方式的流程图；Fig. 2 is a flow chart of a specific implementation method of randomly selecting genes among the genes to encode genes for each individual provided by the embodiment of the present invention;
图3为本发明实施例提供的一种对父代种群进行变异运算的具体实施方式的流程图；Fig. 3 is a flow chart of a specific implementation method of performing mutation operations on parent populations provided by an embodiment of the present invention;
图4为本发明实施例提供的一种对父代种群进行选择运算的具体实施方式的流程图；FIG. 4 is a flow chart of a specific implementation method for selecting a parent population according to an embodiment of the present invention;
图5为本发明实施例提供的另一种对父代种群进行选择运算的具体实施方式的流程图；FIG. 5 is a flowchart of another specific implementation method for selecting a parent population according to an embodiment of the present invention;
图6为本发明实施例提供的一种基于遗传算法的多规格一维套料装置的结构示意图。Fig. 6 is a schematic structural diagram of a multi-standard one-dimensional nesting device based on a genetic algorithm provided by an embodiment of the present invention.
具体实施方式Detailed ways
本发明的核心是提供一种基于遗传算法的多规格一维套料方法及装置，用于从整体角度考虑套料方法，保证在一套原料的分配方案中尽可能达到全局最优解。The core of the present invention is to provide a multi-standard one-dimensional nesting method and device based on genetic algorithm, which is used to consider the nesting method from an overall point of view, so as to ensure that the global optimal solution can be achieved as much as possible in a set of raw material allocation scheme.
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。The following will clearly and completely describe the technical solutions in the embodiments of the present invention with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some, not all, embodiments of the present invention. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.
需要说明的是，本申请的主题所述的“一维”指的是原料和下料均为一维管材，仅在原料长度的维度上进行分配；“多规格”指的是不同的原料的长度可能不同。It should be noted that the "one-dimensional" mentioned in the subject of this application refers to the fact that both the raw material and the cutting material are one-dimensional pipes, which are only distributed in the dimension of the length of the raw material; "multiple specifications" refers to the different raw materials. Length may vary.
图1为本发明实施例提供的一种基于遗传算法的多规格一维套料方法的流程图。如图1所示，基于遗传算法的多规格一维套料方法包括：Fig. 1 is a flow chart of a multi-standard one-dimensional nesting method based on a genetic algorithm provided by an embodiment of the present invention. As shown in Figure 1, the multi-standard one-dimensional nesting method based on genetic algorithm includes:
S10：以原料为个体，以下料为基因，在各基因中随机选择基因对各个体进行编码，得到各个体的基因编码，以获得基因编码的各个体作为初始种群。S10: Taking the raw material as an individual, and the following material as a gene, randomly select a gene from each gene to encode each individual, obtain the gene code of each individual, and obtain each individual encoded by the gene as the initial population.
S11：以初始种群作为父代种群，对父代种群应用交叉运算或变异运算中至少一种运算以及选择运算，直至获得整体适应度满足预设条件的子代种群。S11: Take the initial population as the parent population, apply at least one of crossover operation or mutation operation and selection operation to the parent population until the offspring population whose overall fitness meets the preset conditions is obtained.
其中，原料为未经切割的管材；下料为需要切割产生的管材；整体适应度为一代种群中个体的个体适应度之和；个体适应度为个体利用率；个体利用率为一个原料上分配的下料的长度之和占原料的长度的比值。Among them, the raw material is the uncut pipe; the blank is the pipe that needs to be cut; the overall fitness is the sum of the individual fitness of the individual in the first generation population; the individual fitness is the individual utilization rate; the individual utilization rate is allocated on a raw material The ratio of the sum of the length of the cutting material to the length of the raw material.
对于步骤S10来说，首先假设用于套料地原料管材的数量不足，即长度不能满足下料所需要的管材长度。假设第i根原料Li上排列的下料管材的数量为si，则应满足：For step S10, it is first assumed that the quantity of raw material pipes for nesting is insufficient, that is, the length cannot meet the length of pipes required for blanking. Assuming that the number of blanking pipes arranged on the i-th raw material Li is si , it should satisfy:
即在所有的原料上能够分配的下料的数量不超过所需下料的数量n。That is, the number of cuts that can be allocated on all raw materials Do not exceed the number n of the required blanking.
为了方便进行遗传算法的运算，可以先将原料长度和下料长度排序后建立数据列表。In order to facilitate the operation of the genetic algorithm, the length of the raw material and the length of the cutting material can be sorted first, and then the data list can be established.
具体地，假设共有原料m根，所需的下料n根，分别将原料和下料按长度非递减的顺序排成个体数据列表R[m]＝{L1，L2，……Lm}和基因数据列表P[n]＝{I1，I2，……In}。在此基础上，Li为第i个个体，Ij为第j个基因，每根原料和下料都可以在个体、基因的数据列表中找到。在基因数据列表P[n]中随机选择基因，用基因的下标值对个体进行编码，得到个体基因编码[a1，a2，……ax]，其中1≤x≤n。若个体基因编码为[a，a2，a3]＝[3，0，n-1]，则解码得到[I4，I1，In]。Specifically, assuming that there are m raw materials and n required cutting materials, the raw materials and cutting materials are arranged in the order of non-decreasing length into individual data lists R[m]={L1 , L2 ,...Lm } and gene data list P[n]={I1 , I2 ,...In }. On this basis, Li is the i-th individual, Ij is the j-th gene, and each raw material and cutting material can be found in the individual and gene data lists. Randomly select genes in the gene data list P[n], use the subscript value of the gene to encode the individual, and obtain the individual gene code [a1 , a2 , ... ax ], where 1≤x≤n. If the individual gene is coded as [a, a2 , a3 ]=[3, 0,n -1], [I4 , I1 , In ] can be obtained by decoding.
为了减少非法解，简化计算，在对个体进行编码时，需保证对基因不进行重复选择。In order to reduce illegal solutions and simplify calculations, it is necessary to ensure that genes are not repeatedly selected when encoding individuals.
对所有个体进行基因编码后，生成初始种群。After genetically encoding all individuals, an initial population is generated.
对于步骤S11来说，以个体利用率为个体适应度，个体利用率为一个原料上分配的下料的长度之和占原料的长度的比值。因此个体适应度的函数如下：For step S11, the individual utilization rate is the individual fitness, and the individual utilization rate is the ratio of the sum of the lengths of the cut materials allocated on a raw material to the length of the raw material. So the function of individual fitness is as follows:
其中，Lij为在第i个个体上的第j个基因所代表的下料的长度，为第i个个体上的所有基因所代表的下料的长度之和。f(i)为第i个个体的个体适应度(个体利用率)。Among them, Lij is the length of the cutting material represented by the jth gene on the ith individual, is the sum of the lengths of cuttings represented by all genes on the i-th individual. f(i) is the individual fitness (individual utilization) of the i-th individual.
为了实现对原料管材的利用率最大，目标函数可以为：In order to maximize the utilization of raw material pipes, the objective function can be:
其中，n0≤n(即在任一原料上所能分配的下料的数量的最大值不超过所需下料的总数)；y为余料。余料为将原料管材切割之后剩余的部分，废料为切割后剩下的不可利用的余料。本方案根据企业生产过程中的情况，认为长度小于500mm的余料为废料。一维套料问题的优化目标就是在原料管材都套料的情况下使得下料之后的每根原料管材的废料长度最小。但是一种可能的情况是原料管材的数量充足，因此假定若某根原料管材下料之后的余料长度大于500mm，此余料便不为废料，还能重新作其他用途。Among them, n0 ≤ n (that is, the maximum number of cuttings that can be distributed on any raw material does not exceed the total number of cuttings required); y is the remaining material. The remaining material is the remaining part after cutting the raw material pipe, and the waste material is the unusable remaining material after cutting. According to the situation in the production process of the enterprise, this plan considers the remaining material with a length less than 500mm as waste. The optimization goal of the one-dimensional nesting problem is to minimize the waste length of each raw material pipe after blanking when the material pipes are all nested. However, a possible situation is that the quantity of raw material pipes is sufficient, so it is assumed that if the length of the remaining material after cutting a certain raw material pipe is greater than 500mm, the remaining material is not waste and can be reused for other purposes.
在传统的遗传算法中，从父代种群进化到子代种群，常见的有选择运算、交叉运算和变异运算三种运算方式。在本申请中，为了使种群向整体适应度更大的方向进化，可以对父代种群应用交叉运算或变异运算中至少一种运算(本申请不限定其顺序)以及选择运算，In the traditional genetic algorithm, from the parent population to the offspring population, there are three common operation methods: selection operation, crossover operation and mutation operation. In this application, in order to make the population evolve toward a direction with greater overall fitness, at least one of crossover operations or mutation operations (the order of which is not limited in this application) and selection operations can be applied to the parent population,
其中，选择运算可以采用轮盘赌算法，从而把优化的个体直接传向下一代或者将交叉运算、变异运算之后产生的优秀的个体选择至下一代。交叉运算是在个体之间以基因为单位进行交叉。变异运算是从基因数据列表P[n]中选择新的基因，替换父代个体中的基因。Among them, the selection operation can adopt the roulette algorithm, so that the optimized individuals can be passed directly to the next generation or the excellent individuals generated after the cross operation and mutation operation can be selected to the next generation. The crossover operation is to perform crossover between individuals in units of genes. The mutation operation is to select a new gene from the gene data list P[n] to replace the gene in the parent individual.
以初始种群为父代种群进行运算，得到子代种群，进而可以再以子代种群为父代种群再进行运算得到新的子代种群……根据目标函数(3)，使种群向整体适应度最大的方向进化。为了简化计算，预设条件可以是整体适应度(种群中所有个体的个体适应度之和)达到预设值，也可以是经过预设次数的计算后得到的种群。Use the initial population as the parent population to obtain the child population, and then use the child population as the parent population to perform calculations to obtain a new child population...According to the objective function (3), make the population towards the overall fitness Maximum Direction Evolution. In order to simplify the calculation, the preset condition can be that the overall fitness (the sum of individual fitness of all individuals in the population) reaches a preset value, or the population obtained after a preset number of calculations.
本发明实施例提供的基于遗传算法的多规格一维套料方法，以原料作为个体，以下料作为基因，以利用率作为适应度；随机选择基因对所有个体进行编码从而形成初始种群，相当于获得了一个对所有原料的整体分配方案；再以初始种群作为父代种群，对父代种群应用交叉运算或变异运算中至少一种运算以及选择运算，直至获得整体适应度满足预设条件的子代种群，相当于从全局角度考虑整体分配方案的优劣，从而获得对于多规格原料的套料方案的全局最优解。相比于现有技术中的人工“贪心”算法，从全局角度得到了更加节约原料的方案，且无需实现给出一根原料上所有的套料方案，避免了在原料管材和下料管材规格较多、数量较大时造成的计算复杂、耗时较多的情况，节约了人力，更符合车间生产的实际需要。The multi-specification one-dimensional nesting method based on genetic algorithm provided by the embodiment of the present invention uses raw materials as individuals, following materials as genes, and utilization rate as fitness; randomly select genes to encode all individuals to form an initial population, which is equivalent to Obtain an overall allocation plan for all raw materials; then use the initial population as the parent population, apply at least one of the cross operation or mutation operation and selection operation to the parent population until the child whose overall fitness meets the preset conditions is obtained. Generation population is equivalent to considering the advantages and disadvantages of the overall allocation scheme from a global perspective, so as to obtain the global optimal solution for the nesting scheme of multi-standard raw materials. Compared with the artificial "greedy" algorithm in the prior art, a more raw material-saving scheme is obtained from a global perspective, and there is no need to implement all the nesting schemes on a raw material, avoiding the specification of raw material pipes and blanking pipes The complex calculation and time-consuming situation caused by large quantities and large quantities saves manpower and is more in line with the actual needs of workshop production.
图2为本发明实施例提供的一种在各基因中随机选择基因以对各个体进行基因编码的具体实施方式的流程图。在上述实施例的基础上，在另一实施例中，步骤S10中在在各所述基因中随机选择基因对各所述个体进行编码，得到各所述个体的基因编码具体包括：Fig. 2 is a flow chart of a specific embodiment of randomly selecting genes among the genes to encode genes for each individual provided by the embodiment of the present invention. On the basis of the above-mentioned embodiments, in another embodiment, in step S10, in step S10, genes are randomly selected in each of the genes to encode each of the individuals, and the genetic codes obtained for each of the individuals specifically include:
S20：计算个体的预设基因编码长度。预设基因编码长度为一个个体上能够携带的基因数量的最大值。S20: Calculate the preset genetic code length of the individual. The preset gene encoding length is the maximum number of genes that can be carried by an individual.
S21：随机且不重复地选择多组基因，直至生成的基因编码的数量等于个体的数量。S21: Select multiple groups of genes randomly and without repetition until the number of generated gene codes is equal to the number of individuals.
S22：当基因编码的长度大于预设基因编码长度时，舍弃基因编码。S22: When the length of the gene code is greater than the preset length of the gene code, discard the gene code.
S23：当基因编码的长度小于预设基因编码长度时，在基因编码中随机插入空格以使基因编码的长度等于预设基因编码长度。S23: When the length of the gene code is less than the preset length of the gene code, randomly insert spaces into the gene code so that the length of the gene code is equal to the preset length of the gene code.
在具体实施中，为了防止个体因为基因编码长度不一造成的运算不便，将所有个体的基因编码长度统一。需要说明的是，基因编码长度指的是一个个体上的基因的数量。In the specific implementation, in order to prevent the operation inconvenience caused by the different gene code lengths of individuals, the gene code lengths of all individuals are unified. It should be noted that the gene coding length refers to the number of genes on an individual.
对于步骤S20来说，计算个体的预设基因编码长度，即计算在一个个体上可以容纳的基因的数量的最大值，具体可以通过下式计算得到：For step S20, the preset gene coding length of the individual is calculated, that is, the maximum value of the number of genes that can be accommodated on an individual is calculated, which can be calculated specifically by the following formula:
其中，N为预设基因编码长度，Lm为原料长度的最大值，上式意为将基因按下料长度非递减的顺序进行排列后，从长度最短的下料长度开始加起，直到第N个下料无法在最长的原料上放置为止。Among them, N is the length of the preset gene code, Lm is the maximum length of the raw material, the above formula means that after the genes are arranged in the order of non-decreasing length of the raw material, the length of the shortest raw material is added up to the first N cutting materials cannot be placed on the longest raw material.
对于步骤S21来说，在基因的列表中随机且不重复地选择多组基因，直到为所有个体进行编码。这里不重复地选择，是为了避免产生重复下料的非法解。For step S21, multiple groups of genes are selected randomly and without repetition in the list of genes until all individuals are coded. The purpose of not repeating the selection here is to avoid the illegal solution of repeated blanking.
对于步骤S22来说，由于是随机选择基因，有可能选择的基因编码长度大于预设基因编码长度N，此时需要舍去此基因编码。For step S22, since the gene is randomly selected, it is possible that the selected gene code length is greater than the preset gene code length N, and the gene code needs to be discarded at this time.
对于步骤S23来说，当基因编码长度小于预设基因编码长度N，为了统一运算，可以在基因编码的任意位置插入空格，一个空格代替一个基因，以使基因编码长度等于预设基因编码长度N。For step S23, when the length of the gene code is less than the preset gene code length N, in order to unify the calculation, a space can be inserted at any position of the gene code, and a space can replace a gene, so that the gene code length is equal to the preset gene code length N .
为了进一步减少在基因编码过程中产生的非法解，还可以包括：In order to further reduce illegal solutions generated during genetic coding, it can also include:
S24：当个体携带的基因所代表的下料的长度之和大于个体所代表的原料的长度时，重新对个体进行编码。S24: When the sum of the lengths of the trimmings represented by the genes carried by the individual is greater than the length of the raw material represented by the individual, re-encode the individual.
需要说明的是，步骤S24除了在进行基因编码时起去除非法解的作用，在之后对种群进行交叉、变异运算时也可以作为约束条件去除非法解，减少无用的运算。步骤S24具体可以用下式表示：It should be noted that step S24 not only removes illegal solutions when performing genetic coding, but also serves as a constraint to remove illegal solutions and reduce useless operations when performing crossover and mutation operations on the population. Step S24 can specifically be represented by the following formula:
其中，Ik为在第i个个体Li上的基因所代表的下料的长度。Among them, Ik is the length of cutting material represented by the gene on the i-th individual Li .
本发明实施例提供的基于遗传算法的多规格一维套料方法，通过统一基因编码长度，去除非法解，保证了基因编码的合理性，大大简化了之后种群在进化过程中的运算。The multi-standard one-dimensional nesting method based on the genetic algorithm provided by the embodiment of the present invention ensures the rationality of the gene code by unifying the length of the gene code and removing illegal solutions, and greatly simplifies the operation of the subsequent population evolution process.
在上述实施例的基础上，在另一实施例中，对父代种群进行交叉运算，具体为对父代种群中的父代个体按个体适应度非递增的方式进行排序，对相邻的父代个体两两之间以基因为单位进行交叉运算。On the basis of the above-mentioned embodiment, in another embodiment, the cross operation is performed on the parent population, specifically sorting the parent individuals in the parent population in a non-increasing manner of individual fitness, and sorting the adjacent parent population The cross operation is performed between the generation individuals in units of genes.
在具体实施中，对父代种群进行交叉运算可以是将父代个体排成一队，对相邻的父代个体两两之间进行交叉运算。为了避免产生过多非法解(如不满足式(5))，可以将父代个体按个体适应度非递增的方式进行排序，或者将父代个体按照所代表的原料的长度非递增的方式排序，使相邻的父代个体的差异较小，从而减小产生非法解的几率。In a specific implementation, performing the cross operation on the parent population may be arranging the parent individuals in a line, and performing the cross operation on pairs of adjacent parent individuals. In order to avoid too many illegal solutions (such as not satisfying formula (5)), the parent individuals can be sorted in a non-increasing way of individual fitness, or the parent individuals can be sorted in a non-increasing way according to the length of the raw materials represented , so that the difference between adjacent parent individuals is small, thereby reducing the probability of illegal solutions.
对相邻的父代个体两两之间以基因为单位进行交叉运算，具体可以包括：选择交叉点；由两个相邻的父代个体之间交换交叉点之前的基因产生两个子代个体。即对于子代来说，一个子代在交叉前前边的基因从一个父代的基因中得到，在交叉点后边的基因从另一个父代的基因中得到，通过这种方式由相邻的两个父代个体生成两个子代个体。The crossover operation is performed on the basis of genes between adjacent parent individuals, which may specifically include: selecting an intersection point; exchanging genes before the intersection point between two adjacent parent individuals to generate two offspring individuals. That is to say, for the offspring, the gene in front of a child before the crossover is obtained from the gene of one parent, and the gene behind the intersection is obtained from the gene of the other parent. A parent individual produces two offspring individuals.
图3为本发明实施例提供的一种对父代种群进行变异运算的具体实施方式的流程图。如图3所示，在上述实施例的基础上，在另一实施例中，对父代种群进行变异运算，具体包括：Fig. 3 is a flow chart of a specific implementation manner of performing mutation operations on parent populations provided by an embodiment of the present invention. As shown in Figure 3, on the basis of the above embodiment, in another embodiment, the mutation operation is performed on the parent population, which specifically includes:
S30：随机选择一个基因。S30: Randomly select a gene.
S31：判断父代种群中是否包括此基因；如果是，则返回步骤S30；如果否，进入步骤S32。S31: Determine whether the gene is included in the parent population; if yes, return to step S30; if not, enter step S32.
S32：在父代种群中选择一个基因进行替换。S32: Select a gene in the parent population for replacement.
在基因数据列表P[n]中随机选择一个基因，为了防止重复计算并避免产生非法解，进行步骤S31，判断父代种群中是否包括这个随机选择的基因。如果这个随机选择的基因不存在于父代种群中，说明这是一个新的基因，因此可以将之与父代种群中的一个基因进行替换，使之变异为新的个体。在替换时，应当遵循式(5)。并且，为了使种群向整体适应度高的方向进化，可以先在判断新的基因代表的下料的长度大于被替换的基因代表的下料的长度后再进行替换。Randomly select a gene in the gene data list P[n], in order to prevent double counting and avoid illegal solutions, proceed to step S31 to determine whether the randomly selected gene is included in the parent population. If the randomly selected gene does not exist in the parent population, it means that it is a new gene, so it can be replaced with a gene in the parent population to mutate it into a new individual. When replacing, formula (5) should be followed. Moreover, in order to make the population evolve toward a direction with a high overall fitness, it is possible to replace it after judging that the length of the cutout represented by the new gene is greater than the length of the cutout represented by the replaced gene.
为了方便在父代种群中检查是否包含这个随机选择的基因，在步骤S31之前，还可以包括：In order to check whether this randomly selected gene is included in the parent population for convenience, before step S31, it may also include:
以父代种群中的所有基因构造平衡二叉树结构。Construct a balanced binary tree structure with all genes in the parent population.
具体地可以将基因的下标值构造为平衡二叉树，构造方式如下：Specifically, the subscript value of the gene can be constructed as a balanced binary tree, and the construction method is as follows:
首先构造一颗空树，将首元素作为根节点插入，构造第一个节点，往树中插入第二个元素，根据有序二叉树的定义，将接下来插入值与节点值进行比较，若插入值大于节点值，就递归插入右子树；若小于节点值，就递归插入左子树。每插入一个结点值就先检查是否因插入而破坏了树的平衡性，即判断此时二叉树的平衡因子，平衡因子是二叉树上结点的左子树深度减去右子树深度的值，当二叉树的平衡因子不为-1、0、1时，认为树不平衡，找出当前的最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。在遍历完个体中的所有下标值后，得到一个平衡二叉树结构。First construct an empty tree, insert the first element as the root node, construct the first node, insert the second element into the tree, and compare the next inserted value with the node value according to the definition of an ordered binary tree. If the value is greater than the node value, recursively insert into the right subtree; if it is less than the node value, recursively insert into the left subtree. Every time a node value is inserted, check whether the balance of the tree is destroyed due to the insertion, that is, to judge the balance factor of the binary tree at this time. The balance factor is the value of the depth of the left subtree of the node on the binary tree minus the depth of the right subtree. When the balance factor of the binary tree is not -1, 0, or 1, the tree is considered unbalanced, and the current minimum unbalanced subtree is found. On the premise of maintaining the characteristics of the binary sorting tree, adjust the link relationship between the nodes in the minimum unbalanced subtree, and perform corresponding rotation to make it a new balanced subtree. After traversing all subscript values in the individual, a balanced binary tree structure is obtained.
本发明实施例通过将父代种群中所有的基因的下标值构造为平衡二叉树，在检查随机选择的基因是否为新的基因时，更方便对父代种群的基因的遍历。In the embodiment of the present invention, by constructing the subscript values of all genes in the parent population as a balanced binary tree, it is more convenient to traverse the genes of the parent population when checking whether a randomly selected gene is a new gene.
为了减轻查找压力，还可以在基因编码时，每当选中一个基因，就将其从基因数据列表P[n]中删除，当其被替换下来后再重新放回。这样可以保证在基因数据列表P[n]中随机选择的基因为新的基因。In order to reduce the search pressure, it is also possible to delete a gene from the gene data list P[n] whenever a gene is selected during gene encoding, and put it back when it is replaced. This can ensure that the randomly selected gene in the gene data list P[n] is a new gene.
图4为本发明实施例提供的一种对父代种群进行选择运算的具体实施方式的流程图。如图4所示，在上述实施例的基础上，在另一实施例中，对父代种群进行选择运算，具体包括：Fig. 4 is a flow chart of a specific implementation manner of selecting a parent population according to an embodiment of the present invention. As shown in Figure 4, on the basis of the above embodiment, in another embodiment, the selection operation is performed on the parent population, which specifically includes:
S40：判断生成的子代种群的整体适应度是否大于父代种群的整体适应度；如果是，则进入步骤S41；如果否，则进入步骤S43。S40: Determine whether the overall fitness of the generated offspring population is greater than the overall fitness of the parent population; if yes, go to step S41; if not, go to step S43.
S41：判断子代种群的整体适应度是否满足预设条件；如果是，则结束；如果否，则进入步骤S42；S41: Determine whether the overall fitness of the offspring population meets the preset condition; if yes, end; if not, enter step S42;
S42：以子代种群为父代种群进行交叉运算或变异运算中的至少一种运算后，对新的父代种群和子代种群进行步骤S40；S42: After performing at least one of cross operation or mutation operation with the child population as the parent population, perform step S40 on the new parent population and child population;
S43：继续对父代种群进行交叉运算或变异运算中的至少一种运算，然后进入步骤S40。S43: Continue to perform at least one of crossover operation or mutation operation on the parent population, and then go to step S40.
需要说明的是，本发明实施例中的步骤S42和步骤S43均可以认为是本发明第一个实施例中的步骤S11的一种情况。It should be noted that both step S42 and step S43 in the embodiment of the present invention can be regarded as a case of step S11 in the first embodiment of the present invention.
选择运算为建立在个体适应度评估的基准上，把优化的个体直接遗传到下一代或通过交叉变异产生新的个体再遗传到下一代。The selection operation is based on the basis of individual fitness evaluation, and the optimized individual is directly inherited to the next generation or a new individual is generated through cross-mutation and then passed on to the next generation.
为了逼近全局最优解，每当产生一个子代种群，就比较这个子代种群的整体适应度与它上一代(父代种群)的整体适应度。如果这个子代种群的整体适应度更高，说明更靠近全局最优解，如果其整体适应度还不满足预设条件的话，就以这个子代种群为父代种群再进行交叉运算或变异运算中的至少一种运算以及选择运算。如果父代种群的整体适应度更高，则舍弃该子代种群，重新以父代种群进行交叉运算或变异运算中的至少一种运算以及选择运算。In order to approach the global optimal solution, whenever a child population is generated, the overall fitness of this child population is compared with the overall fitness of its previous generation (parent population). If the overall fitness of the offspring population is higher, it means that it is closer to the global optimal solution. If the overall fitness does not meet the preset conditions, use the offspring population as the parent population to perform crossover or mutation operations At least one of the operations in and selection operations. If the overall fitness of the parent population is higher, the child population is discarded, and at least one of the crossover operation or the mutation operation and the selection operation are performed on the parent population again.
图5为本发明实施例提供的另一种对父代种群进行选择运算的具体实施方式的流程图。如图5所示，在上述实施例的基础上，在另一实施例中，步骤S40具体包括：Fig. 5 is a flow chart of another specific implementation manner of selecting a parent population according to an embodiment of the present invention. As shown in FIG. 5, on the basis of the above-mentioned embodiments, in another embodiment, step S40 specifically includes:
S50：在子代种群中选择预设数量的个体，计算预设数量的个体的个体适应度之和得到子代部分个体适应度之和。S50: Select a preset number of individuals in the offspring population, and calculate the sum of the individual fitness of the preset number of individuals to obtain the sum of individual fitness of the offspring.
S51：在父代种群中选择预设数量的个体，计算预设数量的个体的个体适应度之和得到父代部分个体适应度之和。S51: Select a preset number of individuals in the parent population, and calculate the sum of the individual fitness of the preset number of individuals to obtain the sum of the individual fitness of the parent population.
S52：判断子代部分个体适应度之和是否大于父代部分个体适应度之和。S52: Determine whether the sum of the individual fitness of the offspring is greater than the sum of the individual fitness of the parent.
其中，步骤S50与步骤S51无顺序关系，且两个步骤中的预设数量是同一个值。在种群的个体数量较大时，计算整体适应度较为不便，因此可以分别在父代种群和子代种群中随机选择预设数量的部分个体计算其个体适应度之和，通过判断子代部分个体适应度之和与父代部分个体适应度之和的大小，可以在一定程度上判断子代种群的整体适应度和父代种群的整体适应度之间的关系，从而更加方便地选择更优的种群作为下一次计算的父代种群。Wherein, step S50 and step S51 have no sequence relationship, and the preset quantity in the two steps is the same value. When the number of individuals in the population is large, it is inconvenient to calculate the overall fitness. Therefore, a preset number of individuals can be randomly selected in the parent population and the offspring population to calculate the sum of their individual fitness. By judging the fitness of some individuals in the offspring The sum of the sum of degrees and the sum of the individual fitness of the parent generation can judge the relationship between the overall fitness of the offspring population and the overall fitness of the parent population to a certain extent, so that it is more convenient to select a better population As the parent population for the next calculation.
图6为本发明实施例提供的一种基于遗传算法的多规格一维套料装置的结构示意图。如图6所示，该基于遗传算法的多规格一维套料装置可因配置或性能不同而产生比较大的差异，可以包括一个或一个以上处理器(central processing units，CPU)610(例如，一个或一个以上处理器)和存储器620，一个或一个以上存储应用程序633或数据632的存储介质630(例如一个或一个以上海量存储设备)。其中，存储器620和存储介质630可以是短暂存储或持久存储。存储在存储介质630的程序可以包括一个或一个以上模块(图示没标出)，每个模块可以包括对计算装置中的一系列指令操作。更进一步地，处理器610可以设置为与存储介质630通信，在基于遗传算法的多规格一维套料装置600上执行存储介质630中的一系列指令操作。Fig. 6 is a schematic structural diagram of a multi-standard one-dimensional nesting device based on a genetic algorithm provided by an embodiment of the present invention. As shown in Figure 6, the multi-standard one-dimensional nesting device based on the genetic algorithm may have relatively large differences due to different configurations or performances, and may include one or more processors (central processing units, CPU) 610 (for example, one or more processors) and memory 620, and one or more storage media 630 (such as one or more mass storage devices) for storing application programs 633 or data 632. Wherein, the memory 620 and the storage medium 630 may be temporary storage or persistent storage. The program stored in the storage medium 630 may include one or more modules (not shown in the figure), and each module may include a series of instruction operations on the computing device. Furthermore, the processor 610 may be configured to communicate with the storage medium 630, and execute a series of instruction operations in the storage medium 630 on the multi-standard one-dimensional nesting device 600 based on the genetic algorithm.
基于遗传算法的多规格一维套料装置600还可以包括一个或一个以上电源640，一个或一个以上有线或无线网络接口650，一个或一个以上输入输出接口660，和/或，一个或一个以上操作系统631，例如Windows ServerTM，Mac OS XTM，UnixTM,LinuxTM，FreeBSDTM等等。The multi-standard one-dimensional nesting device 600 based on genetic algorithm may also include one or more power sources 640, one or more wired or wireless network interfaces 650, one or more input and output interfaces 660, and/or, one or more Operating system 631, such as Windows Server™ , Mac OS X™ , Unix™ , Linux™ , FreeBSD™ , etc.
上述图1至图5所描述的基于遗传算法的多规格一维套料方法中的步骤由基于遗传算法的多规格一维套料装置基于该图6所示的结构实现。The steps in the genetic algorithm-based multi-standard one-dimensional nesting method described above in FIG. 1 to FIG. 5 are implemented by the genetic algorithm-based multi-standard one-dimensional nesting device based on the structure shown in FIG. 6 .
所属领域的技术人员可以清楚地了解到，为描述的方便和简洁，上述描述的基于遗传算法的多规格一维套料装置及计算机可读存储介质的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。Those skilled in the art can clearly understand that for the convenience and brevity of the description, the specific working process of the multi-standard one-dimensional nesting device based on the genetic algorithm and the computer-readable storage medium described above can be referred to in the foregoing method embodiment The corresponding process will not be repeated here.
在本申请所提供的几个实施例中，应该理解到，所揭露的方法、装置，可以通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的，例如，模块的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个模块或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，装置或模块的间接耦合或通信连接，可以是电性，机械或其它的形式。作为分离部件说明的模块可以是或者也可以不是物理上分开的，作为模块显示的部件可以是或者也可以不是物理模块，即可以位于一个地方，或者也可以分布到多个网络模块上。可以根据实际的需要选择其中的部分或者全部模块来实现本实施例方案的目的。In the several embodiments provided in this application, it should be understood that the disclosed methods and devices may be implemented in other ways. For example, the device embodiments described above are only illustrative. For example, the division of modules is only a logical function division. In actual implementation, there may be other division methods. For example, multiple modules or components can be combined or integrated. to another system, or some features may be ignored, or not implemented. In another point, the mutual coupling or direct coupling or communication connection shown or discussed may be through some interfaces, and the indirect coupling or communication connection of devices or modules may be in electrical, mechanical or other forms. A module described as a separate component may or may not be physically separated, and a component shown as a module may or may not be a physical module, that is, it may be located in one place, or may also be distributed to multiple network modules. Part or all of the modules can be selected according to actual needs to achieve the purpose of the solution of this embodiment.
另外，在本申请各个实施例中的各功能模块可以集成在一个处理模块中，也可以是各个模块单独物理存在，也可以两个或两个以上模块集成在一个模块中。上述集成的模块既可以采用硬件的形式实现，也可以采用软件功能模块的形式实现。In addition, each functional module in each embodiment of the present application may be integrated into one processing module, each module may exist separately physically, or two or more modules may be integrated into one module. The above-mentioned integrated modules can be implemented in the form of hardware or in the form of software function modules.
集成的模块如果以软件功能模块的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本申请的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，功能调用装置，或者网络设备等)执行本申请各个实施例方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(Read-Only Memory，ROM)、随机存取存储器(Random Access Memory，RAM)、磁碟或者光盘等各种可以存储程序代码的介质。If the integrated modules are realized in the form of software function modules and sold or used as independent products, they can be stored in a computer-readable storage medium. Based on this understanding, the technical solution of the present application is essentially or part of the contribution to the prior art or all or part of the technical solution can be embodied in the form of a software product, and the computer software product is stored in a storage medium , including several instructions to make a computer device (which may be a personal computer, a function calling device, or a network device, etc.) execute all or part of the steps of the methods in various embodiments of the present application. The aforementioned storage medium includes: U disk, mobile hard disk, read-only memory (Read-Only Memory, ROM), random access memory (Random Access Memory, RAM), magnetic disk or optical disk and other various media that can store program codes. .
以上对本发明所提供的一种基于遗传算法的多规格一维套料方法及装置进行了详细介绍。说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。对于实施例公开的装置而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以对本发明进行若干改进和修饰，这些改进和修饰也落入本发明权利要求的保护范围内。A genetic algorithm-based multi-standard one-dimensional nesting method and device provided by the present invention have been described in detail above. Each embodiment in the description is described in a progressive manner, each embodiment focuses on the difference from other embodiments, and the same and similar parts of each embodiment can be referred to each other. As for the device disclosed in the embodiment, since it corresponds to the method disclosed in the embodiment, the description is relatively simple, and for the related information, please refer to the description of the method part. It should be pointed out that for those skilled in the art, without departing from the principles of the present invention, some improvements and modifications can be made to the present invention, and these improvements and modifications also fall within the protection scope of the claims of the present invention.
还需要说明的是，在本说明书中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。It should also be noted that in this specification, relative terms such as first and second are only used to distinguish one entity or operation from another entity or operation, and do not necessarily require or imply that these entities or operations There is no such actual relationship or order between the operations. Furthermore, the term "comprises", "comprises" or any other variation thereof is intended to cover a non-exclusive inclusion such that a process, method, article, or apparatus comprising a set of elements includes not only those elements, but also includes elements not expressly listed. other elements of or also include elements inherent in such a process, method, article, or apparatus. Without further limitations, an element defined by the phrase "comprising a ..." does not exclude the presence of additional identical elements in the process, method, article or apparatus comprising said element.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810620496.0ACN108846480B (en) | 2018-06-15 | 2018-06-15 | A method and device for multi-specification one-dimensional nesting based on genetic algorithm |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810620496.0ACN108846480B (en) | 2018-06-15 | 2018-06-15 | A method and device for multi-specification one-dimensional nesting based on genetic algorithm |
| Publication Number | Publication Date |
|---|---|
| CN108846480Atrue CN108846480A (en) | 2018-11-20 |
| CN108846480B CN108846480B (en) | 2022-03-25 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201810620496.0AActiveCN108846480B (en) | 2018-06-15 | 2018-06-15 | A method and device for multi-specification one-dimensional nesting based on genetic algorithm |
| Country | Link |
|---|---|
| CN (1) | CN108846480B (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111159887A (en)* | 2019-12-27 | 2020-05-15 | 天津博迈科海洋工程有限公司 | Optimized nesting method for modular structural section |
| CN111563393A (en)* | 2019-02-13 | 2020-08-21 | 杭州海康威视数字技术股份有限公司 | Method and device for adjusting modulation depth of card reader based on genetic algorithm |
| CN111832725A (en)* | 2019-04-15 | 2020-10-27 | 电子科技大学 | A method and device for multi-robot multi-task assignment based on improved genetic algorithm |
| CN114036717A (en)* | 2021-10-12 | 2022-02-11 | 华润建筑有限公司 | A cutting plan determination method, device and terminal equipment for steel bar blanking |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP1431956A1 (en)* | 2002-12-17 | 2004-06-23 | Sony France S.A. | Method and apparatus for generating a function to extract a global characteristic value of a signal contents |
| CN101320441A (en)* | 2008-07-18 | 2008-12-10 | 浙江大学 | Combinatorial Optimization Method for Bin Packing Problem |
| CN103279796A (en)* | 2013-06-08 | 2013-09-04 | 苏州大学 | Method for optimizing genetic algorithm evolution quality |
| CN104376369A (en)* | 2014-09-17 | 2015-02-25 | 广东工业大学 | Tire vulcanization workshop energy consumption optimization scheduling method based on hybrid genetic algorithm |
| CN106934485A (en)* | 2017-01-17 | 2017-07-07 | 广东工业大学 | A kind of new one-dimensional based on genetic algorithm rehearses baiting method |
| CN107153880A (en)* | 2016-03-02 | 2017-09-12 | 阿里巴巴集团控股有限公司 | One kind allots procurement practice, device and equipment |
| CN108090650A (en)* | 2017-11-01 | 2018-05-29 | 南京华域云脑信息科技有限公司 | A kind of row's case optimization method based on genetic algorithm |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP1431956A1 (en)* | 2002-12-17 | 2004-06-23 | Sony France S.A. | Method and apparatus for generating a function to extract a global characteristic value of a signal contents |
| CN101320441A (en)* | 2008-07-18 | 2008-12-10 | 浙江大学 | Combinatorial Optimization Method for Bin Packing Problem |
| CN103279796A (en)* | 2013-06-08 | 2013-09-04 | 苏州大学 | Method for optimizing genetic algorithm evolution quality |
| CN104376369A (en)* | 2014-09-17 | 2015-02-25 | 广东工业大学 | Tire vulcanization workshop energy consumption optimization scheduling method based on hybrid genetic algorithm |
| CN107153880A (en)* | 2016-03-02 | 2017-09-12 | 阿里巴巴集团控股有限公司 | One kind allots procurement practice, device and equipment |
| CN106934485A (en)* | 2017-01-17 | 2017-07-07 | 广东工业大学 | A kind of new one-dimensional based on genetic algorithm rehearses baiting method |
| CN108090650A (en)* | 2017-11-01 | 2018-05-29 | 南京华域云脑信息科技有限公司 | A kind of row's case optimization method based on genetic algorithm |
| Title |
|---|
| 刘亚 等: "基于遗传算法的电缆优化分割系统的研究与开发", 《电力科学与工程》* |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111563393A (en)* | 2019-02-13 | 2020-08-21 | 杭州海康威视数字技术股份有限公司 | Method and device for adjusting modulation depth of card reader based on genetic algorithm |
| CN111563393B (en)* | 2019-02-13 | 2022-07-05 | 杭州海康威视数字技术股份有限公司 | Method and device for adjusting modulation depth of card reader based on genetic algorithm |
| CN111832725A (en)* | 2019-04-15 | 2020-10-27 | 电子科技大学 | A method and device for multi-robot multi-task assignment based on improved genetic algorithm |
| CN111832725B (en)* | 2019-04-15 | 2023-05-26 | 电子科技大学 | A method and device for multi-robot multi-task assignment based on improved genetic algorithm |
| CN111159887A (en)* | 2019-12-27 | 2020-05-15 | 天津博迈科海洋工程有限公司 | Optimized nesting method for modular structural section |
| CN111159887B (en)* | 2019-12-27 | 2024-03-19 | 天津博迈科海洋工程有限公司 | Optimized nesting method for module structural section bar |
| CN114036717A (en)* | 2021-10-12 | 2022-02-11 | 华润建筑有限公司 | A cutting plan determination method, device and terminal equipment for steel bar blanking |
| Publication number | Publication date |
|---|---|
| CN108846480B (en) | 2022-03-25 |
| Publication | Publication Date | Title |
|---|---|---|
| CN108320057B (en) | A Flexible Job Shop Scheduling Method Based on Restricted Stable Pairing Strategy | |
| CN108846480A (en) | A kind of one-dimensional nesting method of more specifications and device based on genetic algorithm | |
| CN110472899B (en) | Method and device for distributing articles out of warehouse | |
| CN106484512B (en) | The dispatching method of computing unit | |
| US9047272B1 (en) | System and methods for index selection in collections of data | |
| CN104618134B (en) | A kind of multistage light splitting passive optical network optimization method of power distribution communication net | |
| CN114461386B (en) | Task allocation method and task allocation device | |
| CN104932938A (en) | Cloud resource scheduling method based on genetic algorithm | |
| TW201734831A (en) | Method of assigning application to assigned service cluster and device | |
| CN108776461A (en) | A kind of flexible job shop scheduling method and system | |
| CN109447264B (en) | Virtual machine placement genetic optimization method based on VHAM-R model in cloud computing environment | |
| CN112348323A (en) | Multi-target energy supply and operation flexible scheduling method | |
| CN110868221A (en) | Multi-mode data automatic compression method | |
| CN112631612B (en) | Optimization method for kubernetes cloud platform configuration based on genetic algorithm | |
| CN101706883A (en) | Data mining method and device | |
| CN115018197A (en) | Secondary nesting optimization method and system considering residual material utilization | |
| CN115018387A (en) | Order kneading management method, system, equipment and storage medium | |
| CN115440300B (en) | Codon sequence optimization method and device, computer equipment and storage medium | |
| CN108805288B (en) | One-dimensional nesting method and device and computer readable storage medium | |
| Ndiritu | Reservoir system optimisation using a penalty approach and a multi-population genetic algorithm | |
| Du et al. | A novel self-adaptation and sorting selection-based differential evolutionary algorithm applied to water distribution system optimization | |
| Abidin | Greedy approach for optimizing 0-1 knapsack problem | |
| CN108985439A (en) | A kind of glass typesetting determines method and system | |
| CN115422823A (en) | A Method of Oblique Cutting and Blanking of Wire Rod Based on Parallel Grouping Genetic Algorithm | |
| CN110321208B (en) | Evolutionary computing method for solving cloud task scheduling |
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |