网格搜索（连续问题）

求下面函数的最大值(x,y均在-5~5之间)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
clc,clear;
syms x
syms y

%%定义目标函数
z=-3*x^4+2*x^3+3*x^2-2*pi*x-y^2+pi*y+1;
%-5<x<5,-5<y<5
max=-inf;


%%网格搜索
for x=-5:0.1:5
    for y=-5:0.1:5
        z=-3*x^4+2*x^3+3*x^2-2*pi*x-y^2+pi*y+1;
        if z>max
            max=z;
            x_best=x;
            y_best=y;
        end
    end
end
disp(['函数最大值为',num2str(max)])  %8.1603  x_best=-0.8  y_best=1.6

%缩小范围
for x=-0.9:0.01:-0.7
    for y=1.5:0.01:1.7
        z=-3*x^4+2*x^3+3*x^2-2*pi*x-y^2+pi*y+1;
        if z>max
            max=z;
            x_best2=x;
            y_best2=y;
        end
    end
end
disp(['函数最大值为',num2str(max)]) %8.1631   x_best2=-0.84  y_best2=1.57

%进一步缩小范围
for x=-0.85:0.001:-0.86
    for y=1.56:0.001:1.58
        z=-3*x^4+2*x^3+3*x^2-2*pi*x-y^2+pi*y+1;
        if z>max
            max=z;
            x_best2=x;
            y_best2=y;
        end
    end
end
disp(['函数最大值为',num2str(max)]) %8.1631

流水线加工问题（排队问题）

描述

2023.7.30徐佬例题（最终解释权归徐佬所有）

现有一条生产流水线，顺序排列了两台加工设备，分别为构造器和组装器。有一组不同的
零件需要加工，须按步骤经过这两个工序才能够完成生产。每个零件在不同的生产工序上花
费的时间不同，要求最佳的零件生产顺序，使得总耗时最短。零件顺序一经确定，实际生产
时不允许插队。前一个零件加工未完成时，后一个零件不允许通过，必须在原设备处等待。
等待时后续零件不允许进入该设备。假设零件在流水线上移动不耗费时间。

问题1

有如下10个零件，完成这个问题（全搜索）

零件编号 构造工序耗时 组装工序耗时
1 100 200
2 300 100
3 300 300
4 400 500
5 150 230
6 450 200
7 350 250
8 260 120
9 170 230
10 160 500

matlab代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
%%仿真函数 输入零件加工顺序和零件加工时间，输出总的最小时间
%function t_min=simulate(sequence,process_time)

clc,clear;

tic

a=perms(reshape(1:10,1,10));
t_min=inf;
for i=1:length(a(:,1))
    sequence=a(i,:)';


    process_time=[
        100	200
        300	100
        300	300
        400	500
        150	230
        450	200
        350	250
        260	120
        170	230
        160	500
        ];

    %%开始仿真
    %初始化工作状态
    work_status={'加工设备','构造器','组装器';
        '包含的零件编号',0,0;
        '仍需加工时间',0,0};

    %初始化完成情况
    part_finshed=zeros(10,1);

    %初始化零件指针
    part_point=0;

    %初始化时间
    t_total=0;

    while ~all(part_finshed)
        %如果构造器中没有零件，放入
        if isequal(work_status{2,2},0)&&part_point<size(sequence,1)
            part_point=part_point+1;
            %取出零件编号
            part_num=sequence(part_point);
            work_status{2,2}= part_num;
            work_status{3,2}=process_time(part_num,1);
        end



        %%如果组装器中没有零件，分类器中零件进入组装器
        if isequal(work_status{2,3},0)
            %完成构造器中的加工
            t=work_status{3,2};
            t_total=t+t_total;

            %进入组装器
            work_status{2,3}=work_status{2,2};
            work_status{3,3}=process_time(part_num,2);
            work_status{2,2}=0;
            work_status{3,2}=0;

            continue
        end

        %%组装器中零件完成加工，然后离开组装器
        if work_status{3,2}>=work_status{3,3}
            t=work_status{3,3};
            t_total=t+t_total;
            part_finshed(sequence==work_status{2,3})=1;
            work_status{3,2}=work_status{3,2}-work_status{3,3};
            work_status{2,3}=0;
            work_status{3,3}=0;

        else
            t=work_status{3,3};
            t_total=t+t_total;
            part_finshed(sequence==work_status{2,3})=1;
            work_status{3,2}=0;
            work_status{2,3}=0;
            work_status{3,3}=0;
        end

    end
    if t_total<t_min
        t_min=t_total;
        sequence_final=sequence;
    end
end
toc
disp(['花费最短时间为',num2str(t_min),'分钟']);

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
历时 82.181133 秒。
花费最短时间为2960分钟
sequence=[
1
10
4
6
9
8
5
7
3
2];

问题2

有如下40个零件，完成这个问题（①随机搜索/蒙特卡洛②遗传算法）

零件编号 构造工序耗时 组装工序耗时
1 180 45
2 120 75
3 20 180
4 70 165
5 70 196
6 160 165
7 170 270
8 190 150
9 180 255
10 160 300
11 360 30
12 180 55
13 180 30
14 40 40
15 280 70
16 400 100
17 180 85
18 200 70
19 200 100
20 120 35
21 255 150
22 105 30
23 165 360
24 15 390
25 60 210
26 90 450
27 180 210
28 255 60
29 285 330
30 300 510
31 210 35
32 225 50
33 45 15
34 135 80
35 210 70
36 240 70
37 240 15
38 285 100
39 165 100
40 210 100

随机搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
%%仿真函数 输入零件加工顺序和零件加工时间，输出总的最小时间
%function t_min=simulate(sequence,process_time)

clc,clear;

tic


t_min=inf;
for i=1:1000000
    sequence=randperm(40)';


    process_time=[
        180	45
        120	75
        20	180
        70	165
        70	196
        160	165
        170	270
        190	150
        180	255
        160	300
        360	30
        180	55
        180	30
        40	40
        280	70
        400	100
        180	85
        200	70
        200	100
        120	35
        255	150
        105	30
        165	360
        15	390
        60	210
        90	450
        180	210
        255	60
        285	330
        300	510
        210	35
        225	50
        45	15
        135	80
        210	70
        240	70
        240	15
        285	100
        165	100
        210	100];

        

    %%开始仿真
    %初始化工作状态
    work_status={'加工设备','构造器','组装器';
        '包含的零件编号',0,0;
        '仍需加工时间',0,0};

    %初始化完成情况
    part_finshed=zeros(10,1);

    %初始化零件指针
    part_point=0;

    %初始化时间
    t_total=0;

    while ~all(part_finshed)
        %如果构造器中没有零件，放入
        if isequal(work_status{2,2},0)&&part_point<size(sequence,1)
            part_point=part_point+1;
            %取出零件编号
            part_num=sequence(part_point);
            work_status{2,2}= part_num;
            work_status{3,2}=process_time(part_num,1);
        end



        %%如果组装器中没有零件，分类器中零件进入组装器
        if isequal(work_status{2,3},0)
            %完成构造器中的加工
            t=work_status{3,2};
            t_total=t+t_total;

            %进入组装器
            work_status{2,3}=work_status{2,2};
            work_status{3,3}=process_time(part_num,2);
            work_status{2,2}=0;
            work_status{3,2}=0;

            continue
        end

        %%组装器中零件完成加工，然后离开组装器
        if work_status{3,2}>=work_status{3,3}
            t=work_status{3,3};
            t_total=t+t_total;
            part_finshed(sequence==work_status{2,3})=1;
            work_status{3,2}=work_status{3,2}-work_status{3,3};
            work_status{2,3}=0;
            work_status{3,3}=0;

        else
            t=work_status{3,3};
            t_total=t+t_total;
            part_finshed(sequence==work_status{2,3})=1;
            work_status{3,2}=0;
            work_status{2,3}=0;
            work_status{3,3}=0;
        end

    end
    if t_total<t_min
        t_min=t_total;
        sequence_final=sequence;
    end
end
toc
disp(['花费最短时间为',num2str(t_min),'分钟']);

结果

1
2
3
历时 24.543905 秒。
花费最短时间为1145分钟
final_sequence略

遗传算法

  • GA.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
clc,clear;
tic
%%导入数据
    process_time=[
        180	45
        120	75
        20	180
        70	165
        70	196
        160	165
        170	270
        190	150
        180	255
        160	300
        360	30
        180	55
        180	30
        40	40
        280	70
        400	100
        180	85
        200	70
        200	100
        120	35
        255	150
        105	30
        165	360
        15	390
        60	210
        90	450
        180	210
        255	60
        285	330
        300	510
        210	35
        225	50
        45	15
        135	80
        210	70
        240	70
        240	15
        285	100
        165	100
        210	100];



%%设置遗传算法参数

%迭代次数
geneation_number=100;
%变异概率
mutate_rate=0.15;
%种群大小
population_size=20;


%%初始化种群
population=cell(population_size,2);
for i=1:population_size
    %随机给出一组解
    population{i,1}=init();
    %计算适应度函数
    population{i,2}=fitnessfun(population{i,1},process_time);

end

%%遗传寻优
for j=1:geneation_number
    %交配产生新子代
    new_population=exchange(population);
    %变异
    for k=1:size(new_population,1)
        if rand<mutate_rate
        new_population{k,1}=mutate(population{k,1});
        end
    end

    %计算新种群适应度
    for m=1:size(new_population,1)
    new_population{m,2}=fitnessfun(new_population{m,1},process_time);
    end

    %合并种群
    population_sum=[population;new_population];

    %保留优势个体
    for n=1:size(population_sum,1)
        fitness_list(n)=population_sum{n,2};
    end

    [fitness_list,idx]=sort(fitness_list);

    for s=1:population_size
        population{s,1}=population_sum{idx(s),1};
        population{s,2}=population_sum{idx(s),2};
    end

end

toc

disp(['花费最短时间为',num2str(population{1,2}),'分钟']);
disp('零件加工顺序为');
disp(population{1,1});
  • init.m
1
2
function popu=init()
popu=randperm(40)';
  • fitnessfun.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
%%仿真函数 输入零件加工顺序和零件加工时间，输出总的最小时间
function t_total=fitnessfun(sequence,process_time)


    %%开始仿真
    %初始化工作状态
    work_status={'加工设备','构造器','组装器';
        '包含的零件编号',0,0;
        '仍需加工时间',0,0};

    %初始化完成情况
    part_finshed=zeros(10,1);

    %初始化零件指针
    part_point=0;

    %初始化时间
    t_total=0;

    while ~all(part_finshed)
        %如果构造器中没有零件，放入
        if isequal(work_status{2,2},0)&&part_point<size(sequence,1)
            part_point=part_point+1;
            %取出零件编号
            part_num=sequence(part_point);
            work_status{2,2}= part_num;
            work_status{3,2}=process_time(part_num,1);
        end



        %%如果组装器中没有零件，分类器中零件进入组装器
        if isequal(work_status{2,3},0)
            %完成构造器中的加工
            t=work_status{3,2};
            t_total=t+t_total;

            %进入组装器
            work_status{2,3}=work_status{2,2};
            work_status{3,3}=process_time(part_num,2);
            work_status{2,2}=0;
            work_status{3,2}=0;

            continue
        end

        %%组装器中零件完成加工，然后离开组装器
        if work_status{3,2}>=work_status{3,3}
            t=work_status{3,3};
            t_total=t+t_total;
            part_finshed(sequence==work_status{2,3})=1;
            work_status{3,2}=work_status{3,2}-work_status{3,3};
            work_status{2,3}=0;
            work_status{3,3}=0;

        else
            t=work_status{3,3};
            t_total=t+t_total;
            part_finshed(sequence==work_status{2,3})=1;
            work_status{3,2}=0;
            work_status{2,3}=0;
            work_status{3,3}=0;
        end

    end
  • exchange.m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function new_population=exchange(population)

population_size=size(population,1);

for i=1:population_size/2
    father=population{2*i-1,1};
    mother=population{2*i,1};
    son=father;
    dauther=mother;
   
    for j=1:length(son)
        if rand>0.5
            a=son(j);
            b=dauther(j);
            idx_a=dauther==a;
            idx_b=son==b;
            son(j)=b;
            dauther(j)=a;
            t=dauther(idx_a);
            dauther(idx_a)=son(idx_b);
            son(idx_b)=t;
        end
    end
    new_population{2*i-1,1}=son;
    new_population{2*i,1}=dauther;
end


for i=1:population_size
    new_population{i,2}=inf;
end

  • mutate.m
1
2
3
4
5
6
7
8
9
10
function popu=mutate(popu)

for i=1:length(popu)
    if rand<0.2
        a=randi(length(popu));
        t=popu(a);
        popu(a)=popu(i);
        popu(i)=t;
    end
end

结果

1
2
3
历时 0.186415 秒。
花费最短时间为1091分钟
零件加工顺序略