I-Corps: Deep-Scale Evolution for Industrial Shape Nesting

这个I-Corps项目的更广泛的影响/商业潜力是开发一种制造方法，可以减少50%的材料浪费。从昂贵的基材（钢、钛、皮革、复合材料）上切割异形件的制造商使用形状嵌套软件在基材毛坯和残余物上安装尽可能多的件，以尽量减少材料浪费。然而，目前的形状嵌套软件往往不能达到最佳的材料使用。目前的产品按顺序嵌套形状，将每片一个接一个地放置在基板上。所提出的技术旨在更有效地改善二维基板上物品的放置。该技术的基础是模拟多个相互依赖的物种进化成一个紧密结合、稳定和多产的生态系统。其结果是大量减少了浪费的材料。例如，在汽车工业中，拟议中的技术可能会更紧密地将车身部件从钢板上切割下来，从而减少所需的原钢和废钢的数量，后者需要大量的能量来熔化和再利用。这项技术可以应用于布料和皮革（纺织品），铝和钢（造船），或钛和复合材料（航空航天）。废料的减少可能会提高美国经济的效率，提高工人的生产率。减少对开采金属的需求可能对环境有利，减少对填埋空间的需求也会有好处（因为修剪后的废料往往无法使用）。更有效地利用原材料制造零部件，可以提供可持续的资源管理、节约能源、减少温室气体排放、减少污染和对生态系统的压力，并使消费者更能负担得起最终产品。这个I-Corps项目基于一种算法的开发，该算法用于模拟使用生态系统策略的合作进化。提出的深度进化算法采用大规模并行同时考虑全局布局模式，这是一种不同于现有嵌套产品中使用的顺序块放置和局部布局决策的新方法。数以百万计的物种（在二维筑巢中，每个物种都可能在平面基底上放置一个形状的碎片）竞争覆盖二维材料。最大的合作（即非竞争）物种出现了。从生态系统的角度来看，比起个体的、局部成功的物种，更倾向于大规模的合作物种。共同进化的选择压力将种群推向全局最优的总解决方案。这种强调解决方案组件的协作组通常会找到更紧密、更有效的2D形状嵌套（或3D部件的包装），而不是当前的顺序技术，即一次放置一个形状，或先打包一个项目再打包下一个项目。最近的研究比较了商业2D形状嵌套软件产品的一个问题，表明所提出的技术嵌套了12个零件，而商业产品只嵌套了10个或11个零件。所提出的技术在速度和输出质量方面的性能可用于从工业中扩展到更大的嵌套问题。基于种群的进化，该算法具有固有的大规模并行性。与深度学习神经网络一样，所提出的方法依赖于图形处理单元（gpu）计算能力的指数增长。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The broader impact/commercial potential of this I-Corps project is the development of an approach to manufacturing that may reduce material waste by fifty percent (50%). Manufacturers cutting shaped pieces from expensive substrates (steel, titanium, leather, composites) use shape nesting software to fit as many pieces as possible on substrate blanks and remnants to minimize wasted material. However, current shape nesting software often falls short of optimal material usage. Current products nest shapes sequentially, placing each piece on the substrate one after another. The proposed technology is designed to improve the placement of items on a 2D substrate more efficiently. The technology is based on the simulated evolution of multiple, inter-dependent species into a tightly knit, stable and productive ecosystem. The result is a substantial reduction in wasted material. In the auto industry, for example, the proposed technology may more tightly nest body parts to be cut from steel sheets, reducing the amount of raw steel needed as well as the scrap steel, which requires substantial energy to melt and reuse. The technology may be applied to cloth and leather (textiles), aluminum and steel (shipbuilding), or titanium and composites (aerospace). The reductions in scrap may make the US economy more efficient and workers more productive. Reduced demand for mined metals may have environmental benefits, as will the reduced need for landfill space (since trim waste is often unusable). More efficient manufacturing of parts from raw materials may provide for sustainable resource management, save energy, lower greenhouse gas emissions, reduce pollution and the strain on ecosystems, and make final products more affordable for consumers.This I-Corps project is based on the development of an algorithm for simulating evolution of cooperation using an ecosystem strategy. The proposed algorithm for deep-scale evolution uses massively-parallel simultaneous consideration of global layout patterns, a new approach distinct from the sequential piece placement and local layout decisions used in available nesting products. Millions of species (each a possible placement of a shaped piece on a flat substrate in 2D nesting) compete to cover the 2D material. The biggest set of cooperating (i.e., non-competing) species emerges. The ecosystem perspective favors large sets of cooperative species over individual, locally successful species. Co-evolutionary selection pressure pushes the population toward globally optimal total solutions. This emphasis on cooperative groups of solution components often will find tighter, more efficient nestings of 2D shapes (or packings of 3D pieces) than current sequential techniques that place one shape at a time, or pack one item before the next. Recent studies comparing commercial 2D shape nesting software products on one problem showed that the proposed technology nested twelve pieces, while the commercial product offerings nested only ten or eleven. The performance of the proposed technology for both speed and output quality may be used to scale up to larger nesting problems from industry. Based on the evolution of populations, the algorithm is inherently massively parallel. As with deep learning neural networks, the proposed approach depends on the exponential growth in computing power of graphics processing units (GPUs).This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.