设为首页收藏本站

中国膜结构网

 找回密码
 立即注册
膜结构车棚
膜结构车棚膜结构资质国产膜材 膜结构网中国膜结构协会
查看: 72|回复: 0

矩形排样问题 遗传算法解决方案

[复制链接]
  • TA的每日心情
    开心
    2020-8-10 08:21
  • 签到天数: 1263 天

    连续签到: 15 天

    [LV.10]以坛为家III

    发表于 2020-7-12 10:17 | 显示全部楼层 |阅读模式
    最近在实习中,遇到了一个实际问题。客户要将若干大小不一的小矩形,排到大矩形上,而且还要求可以设置小矩形之间的间距,和大矩形的margin值,便于裁切。

    排样问题是一个经典的NP问题,有很多解决方案。神经网络、遗传、蚁群、模拟退火等等算法都可以解决这个问题。对于一些行业的工业生产,很多生产数据并没有测试数据那般刁钻,所以这些算法基本都能满足生产的需要。



    在这里,我主要参考了一篇郑州大学的研究生毕业论文,自己又稍加了修改,用遗传算法解决了这个问题。



    遗传算法的本质其实就是把问题简化为一个个序列,根据一定规律随机生成后,拿这个编码序列贪心的得出解,然后不断的迭代,优胜劣汰,向最优解靠拢。

    我认为遗传算法有几个关键之处:编码规则、初始种群的选取、贪心方式、适应度函数的选择、变异规则。

    1.好的编码规则能便于程序的实现,同时也决定了程序的贪心结构,在这里,我的编码是1-n的阿拉伯数字,代表放入的矩形的编号,从左到右是放入的顺序。如果矩形需要旋转,则为负数。

    2.初始种群的选取,给矩形按照权值排序,权值=0.9*矩形面积+0.1*矩形长宽比,大的先放,小的后放,然后随机其正负值,生成初始种群,好的初始种群能很快就找到最优解。

    3.我的贪心解决方案就是最低水平线算法,从左到右,从下到上,不断的寻找能放入的点。每次放入一个新点后,把未来的矩形可能的存在的点加入一个有序的序列中,后面的待排矩形就在这个序列里寻找可以放的点。

    4.适应度函数,两个个体好坏的决定因素,在这里,我设置了3个决定因素,首先是放入的矩形面积占待放入的矩形面积的百分比,第二个是当前排入的矩形的最大高度,第三个是排入矩形的整齐程度(高的种类个数)。我还有一些新想法,比如比较新图形的重心,重心越靠左下约好,能避免一些相同适应值下的非最优解。

    5.变异规则,这里用了4种变异方案,交叉、单点。。。。。。不详述了。



    #ifndef LAYOUTALGORYTHM_H
    #define LAYOUTALGORYTHM_H

    #include <iostream>
    #include <stdio.h>
    #include <math.h>
    #include <stdlib.h>
    #include <string>
    #include <string.h>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <set>
    #include <map>
    #include <stack>
    #include <QDebug>
    using namespace std;
    #include "layoutalgorythmglobal.h"

    class LayoutAlgorythm;
    struct MyPoint{
        double x,y;
        MyPoint(){}
        MyPoint(double ix,double iy){
            x=ix;
            y=iy;
        }
        friend bool operator<(const MyPoint&a ,const MyPoint &b){
            //按照y值排序,y相等时按照x排
            if(a.y==b.y)return a.x<b.x;
            else return a.y<b.y;
        }
    };

    struct MyRect{
        double width,height,S;
        double ratio;
        int index;
        MyRect(){}
        MyRect(double iWidth,double iHeight,int iIndex){
            width=iWidth;
            height=iHeight;
            S=iWidth*iHeight;
            ratio=max(height/width,width/height);
            index=iIndex;
        }
        MyRect(double iWidth,double iHeight){
            width=iWidth;
            height=iHeight;
            S=iWidth*iHeight;
            ratio=max(height/width,width/height);
        }
        friend bool operator<(const MyRect &iRectA , const MyRect &iRectB){
            double PriorityA=LayoutAlgorythmGlobal::m_weightArea*iRectA.S+LayoutAlgorythmGlobal::m_weightRatio*iRectA.ratio;
            double PriorityB=LayoutAlgorythmGlobal::m_weightArea*iRectB.S+LayoutAlgorythmGlobal::m_weightRatio*iRectB.ratio;
            return PriorityA>PriorityB;
            //大的靠前
            //Priority=WeightArea*R[i].S+WeightRatio*R[i].(L/W)
        }
    };

    struct Individual
    {
        int m_order[100];//顺序,有正负,没有0
        MyPoint m_position[100];//每个矩形的左下角位置
        double m_val[3];//插入的面积,最高的水平线,获得的高度种类个数
        Individual(){}
        friend bool operator<(const Individual&iIndiA ,const Individual &iIndiB){
            if(iIndiA.m_val[0]==iIndiB.m_val[0]){
                if(iIndiA.m_val[1]==iIndiB.m_val[1]){
                    return iIndiA.m_val[2]<iIndiB.m_val[2];//高度种类越小越好
                }
                else return iIndiA.m_val[1]<iIndiB.m_val[1];//最高水平线越小越好
            }
            else{
                return iIndiA.m_val[0]>iIndiB.m_val[0];//插入的面积越大越好
            }
        }
    };

    class LayoutAlgorythm
    {
    public:
        void setBigRect(const double iW,const double iH);
        void setGap(const double iGap);
        double getGap();
        void setMargin(const double iMargin);
        double getMargin();
        void addRect(const double iW,const double iH,const int index);
        void setRect(int position,MyRect iRect);
        MyRect getRect(int position);
        void dealWithGapMargin();
        void solve();
        void setRectsNum(int n);
        int getRectsNum();
        Individual getResult();
        LayoutAlgorythm(){}
    private:
        //最低水平线算法,by Shijing
        double m_totalS=0;
        int m_num=0;//num_of_small_rect
        Individual m_population[120];
        MyRect m_rects[100];//第0个是container
        double m_gap=0;//矩形之间的间距
        double m_margin=0;//与边框的间距
        void initialize();//生成初始种群按照排序规则初始化后存到population里,并更新fitness值
        int* randPerm(int N);//生成N个不同的1-N的随机数
        void fitness(Individual &myIndi);
        void crossOne(const Individual iFirst,const Individual iSecond, Individual &oFirst, Individual &oSecond);//单点交叉
        void crossTwo(const Individual iFirst,const Individual iSecond, Individual &oFirst, Individual &oSecond);//双点交叉
        void changePosition(const Individual input,Individual &output);//位置变异
        void changeRotate(const Individual input,Individual &output);//旋转变异
    };







    struct randnum
    {
        int index;
        int v;
        friend bool operator<(const randnum&a,const randnum&b){
            return a.v<b.v;
        }
    };


    #endif // LayoutAlgorythm_H
    http://www.mjgw.org/ 专业从事膜结构设计、制作加工、施工安装的膜结构咨询服务,能够为客户提供专业的膜结构整体解决方案。做中国最好的膜结构综合服务平台。欢迎大家联系QQ:463017170.
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    关闭

    推荐膜材品牌上一条 /5 下一条

    进口膜材 国产膜材 pvdf膜材ptfe膜材ETFE膜材
    最好的膜结构公司 一级膜结构资质 膜结构一级资质
    膜结构设计-膜结构十大品牌-etfe设计-充气膜结构
    诺科膜结构
    遨都膜结构设计
    中国膜结构网
    中国空间膜结构协会

    QQ|申请友链|Archiver|手机版|中国膜结构论坛

    GMT+8, 2020-8-10 10:14 , Processed in 0.227495 second(s), 23 queries .

    Powered by 中国膜结构网->膜材采购->膜结构设计->膜结构安装->膜结构维修

    © 2014-2020 膜结构协会->进口膜材->国产膜材->PVDF膜材->PTFE膜材->ETFE膜材.

    快速回复 返回顶部 返回列表