Processing of multi-objective programming
Multi-objective programming refers to the optimization of multiple objective functions that need to be considered simultaneously in an optimization problem. In multi-objective programming problems, objective functions usually conflict with each other, that is, in the process of optimizing one objective function, another or several objective functions may be affected. Therefore, the goal of the multi-objective programming problem is to find a solution x such that all objective functions reach a relatively satisfactory compromise while satisfying the constraints.
In the real world, we often face problems that require trade-offs between multiple goals. For example:
| Scenario | Example |
|---|---|
| Between economic development and environmental protection Seeking balance | For example, the objective function of economic development can be the growth rate of gross domestic product (GDP), while the objective function of environmental protection can be the reduction rate of pollutant emissions. Governments need to balance these two goals when formulating policies to achieve sustainable economic and environmental development. |
| Reducing costs while improving product quality | For example, when designing a mobile phone, designers need to ensure performance, battery life, weight, cost, etc. reach an appropriate balance between factors. |
| Weighing returns and risks in investment and financial management | For example, when buying funds or stocks, investors need to consider the expected returns and risks of different products before purchasing Financial products with appropriate risk levels. |
| Multiple objectives in supply chain management | Such as inventory costs, transportation costs, customer satisfaction, etc. To achieve a balance between these goals, companies need to optimize their production, procurement, transportation and distribution strategies. |
| The game between profit and sales in product pricing | For example, when pricing electronic products, we hope to get the most profit margins, and at the same time we hope to expand sales, so that The unit cost of production is reduced. |
For these multi-objective problems, how to compromise and how to solve them is a difficult problem. For this reason, scholars have proposed many methods to convert multi-objective programming problems into single-objective programming problems so that they can be solved using traditional single-objective optimization techniques. Such as: Weighted sum method (this article), indicator method, hierarchical method, etc. These methods have their own advantages and disadvantages, and when using them, you need to choose the appropriate method according to the characteristics of the specific problem.
It is worth noting that the solution obtained after converting multi-objective into a single objective may not be the Pareto optimal solution of the multi-objective optimization problem (no other solution is better), so various factors need to be weighed in practical applications.
Weighted Sum Method
1. Principle
The Weighted Sum Method is to add multiple objective functions to form a single objective function by assigning different weight values. Specifically, assume that there are
m
m
m objective functions
f
i
(
x
)
,
i
=
1
,
.
.
.
,
m
f_i(x)，i=1,…,m
fi?(x), i=1,…,m, we can construct a new objective function
F
(
x
)
F(x)
F(x) is as follows:
F
(
x
)
=
w
1
?
f
1
(
x
)
+
w
2
?
f
2
(
x
)
+
.
.
.
+
w
m
?
f
m
(
x
)
F(x) = w_1 * f_1(x) + w_2 * f_2(x) + … + w_m * f_m(x)
F(x)=w1f1?(x) + w2f2?(x) + … + wmfm?(x)
in
w
i
w_i
wi? means the first
i
i
The weights of i objective functions usually require the sum of all weights to be 1.
By adjusting the weight value, different optimization results can be obtained.
2. Give examples
Suppose a farmer wants to optimize the layout of crops on his land and needs to balance the following two goals:
- Goal 1: Maximize farm output value (unit: yuan);
- Objective 2: Minimize fertilizer usage (unit: kilogram).
The farmer has two crops to grow: Crop A, Crop B, and Crop C. set up
x
1
x_1
x1?、
x
2
x_2
x2?、
x
3
x_3
x3? are the areas for planting crops A, B, and C respectively.
- It is known that the output values of crops A, B, and C per mu are 1,000 yuan, 1,200 yuan, and 1,300 yuan respectively. Then, the function of objective 1:
maximize
F
1
(
x
)
=
1000
?
x
1
+
1200
?
x
2
+
1300
?
x
3
\text{maximize} \quad F_1(x) = 1000 \cdot x_1 + 1200 \cdot x_2 + 1300 \cdot x_3
maximizeF1?(x)=1000?x1? + 1200?x2? + 1300?x3?.
- Crops A, B, and C require 20 kilograms, 30 kilograms, and 33 kilograms of chemical fertilizers per mu respectively. Then, the function of objective 2:
minimize
F
2
(
x
)
=
20
?
x
1
+
30
?
x
2
+
33
?
x
3
\text{minimize} \quad F_2(x) = 20 \cdot x_1 + 30 \cdot x_2 + 33 \cdot x_3
minimizeF2?(x)=20?x1? + 30?x2? + 33?x3?.
- The total planting area does not exceed 100 acres. Right now,
x
1
+
x
2
+
x
3
≤
100
x_1 + x_2 + x_3 \leq 100
x1? + x2? + x3?≤100.
- Each of the three crops needs to be planted on at least 10 acres.
We can convert this into a single-objective optimization problem using the weighted sum method.
- First, we introduce the weight parameter
w
1
w_1
w1?、
w
2
w_2
w2?, respectively represent the importance of farm output value and fertilizer usage, and satisfy
w
1
+
w
2
=
1
w_1 + w_2 = 1
w1? + w2?=1, that is
w
2
=
1
?
w
1
w_2 = 1 – w_1
w2?=1?w1?
- Then considering that the units and data magnitudes of the two targets are different, we introduce parameters
c
c
c to adjust the order of magnitude for target 2. In actual use, it can also be incorporated into
w
2
w_2
w2?
- Then, the new single target
maximize
F
(
x
)
=
w
1
?
F
1
(
x
)
?
c
?
w
2
?
F
2
(
x
)
\text{maximize} \quad F(x) = w_1 \cdot F_1(x) – c \cdot w_2 \cdot F_2(x)
maximizeF(x)=w1F1?(x)?c?w2F2?(x), that is
maximize
w
1
?
(
1000
?
x
1
+
1200
?
x
2
+
1300
?
x
3
)
?
c
?
w
2
?
(
20
?
x
1
+
30
?
x
2
+
33
?
x
3
)
\text{maximize} \quad w_1 \cdot(1000 \cdot x_1 + 1200 \cdot x_2 + 1300 \cdot x_3) – c \cdot w_2 \cdot (20 \cdot x_1 + 30 \ \cdot x_2 + 33 \cdot x_3)
maximizew1(1000?x1? + 1200?x2? + 1300?x3?)?c?w2(20?x1? + 30?x2? + 33?x3?)
In practical applications, the values of weight parameters w1 and w2 can be adjusted according to the requirements and the order of magnitude of the data to balance these two goals. Assuming that the farmer is more concerned about farm output value, he can choose
w
1
=
0.7
w_1 = 0.7
w1?=0.7.
Next, we use the MindOpt APL modeling language to model this problem and call the MindOpt Solver to solve it. code show as below:
clear model; # ------Modeling-------Start----- # model_1.mapl #Variables var x1 >= 10; var x2 >= 10; var x3 >= 10; # Weight parameter param w1 = 0.7; # Assume that the farmer is more concerned about the farm output value param w2 = 1 - w1; param c = 50; # Simple estimate based on the order of magnitude difference 1000/20 = 50 # Target maximize obj: w1 * (1000 * x1 + 1200 * x2 + 1300 * x3) - c * w2 * (20 * x1 + 30 * x2 + 33 * x3); #Define constraints subject to constraint1: x1 + x2 + x3 <= 100; # ------Modeling-------End----- #solve option solver mindopt; # (optional) Specify the solver used for solution, the default is MindOpt option mindopt_options 'print=0'; #Set the solver output level to reduce process printing solve; # solve # Result printing and checking results print "-----------------Display---------------"; display; print "The single-objective optimum of the transformation is:",w1 * (1000 * x1 + 1200 * x2 + 1300 * x3) - c * w2 * (20 * x1 + 30 * x2 + 33 * x3); print "Among them, species", x1,"acre of crop A, species",x2,"acre of crop B, species",x3,"acre of crop C."; print "Corresponding farm output value:", (1000 * x1 + 1200 * x2 + 1300 * x3),"Yuan."; print "Corresponding fertilizer usage:", (20 * x1 + 30 * x2 + 33 * x3),"Kilograms.";
The result of running the above code is as follows:
Running mindoptampl
wantsol=1
print=0
MindOpt Version 0.25.1 (Build date: 20230816)
Copyright (c) 2020-2023 Alibaba Cloud.
Start license validation (current time : 22-SEP-2023 16:14:25).
License validation terminated. Time: 0.006s
OPTIMAL; objective 41100.00
0 simplex iterations
Completed.
------------------Display--------------
Primal Solution:
x1 = 10.0000000
x2 = 10.0000000
x3 = 80.0000000
The optimal single objective of the transformation is: 41099.99999999999
Among them, 10 acres are planted to crop A, 10 acres are planted to crop B, and 80 acres are planted to crop C.
Corresponding farm output value: 126,000 yuan.
Corresponding fertilizer usage: 3140 kg.
3. Weight impact analysis and improvement
Different parameter settings will result in different results. For example, in the above scheme, if
c
c
c remains unchanged, we choose different
w
w
The value of w, the result is as follows.
| w1 | Evaluation target value | A number of acres | B number of acres | C acres | Farm output value (yuan) | Fertilizer usage (kilograms) |
|---|---|---|---|---|---|---|
| 1.0 | 126000 | 10 | 10 | 80 | 126000 | 3140 |
| 0.9 | 97700 | 10 | 10 | 80 | 126000 | 3140 |
| 0.8 | 69400 | 10 | 10 | 80 | 126000 | 3140 |
| 0.7 | 41100 | 10 | 10 | 80 | 126000 | 3140 |
| 0.65 | 29225 | 80 | 10 | 10 | 105000 | 2230 |
| 0.6 | 18400 | 80 | 10 | 10 | 105000 | 2230 |
| 0.55 | 7575 | 80 | 10 | 10 | 105000 | 2230 |
| 0.5 | -3250 | 10 | 10 | 10 | 35000 | 830 |
| 0.4 | -10900 | 10 | 10 | 10 | 35000 | 830 |
It can be seen that the optimal decision calculated by different weights is different, and there may even be no valid solution.
The weighted sum method that converts multi-objective programming into single-objective programming has the following shortcomings:
- Subjectivity of weight assignment: The process of weighting each goal is subjective and may not accurately reflect the relative importance of the goal.
- Information loss: The weighted sum method combines all targets into a single target, losing information about individual targets and their relationships.
- Limited flexibility: This method assumes a linear relationship between objectives, which may not hold in all cases.
To improve the weighted sum method, the following methods can be considered:
- Use sensitivity analysis: Conduct a sensitivity analysis to determine the impact of different weight assignments on the final solution. This can help determine the range of weights that produce desirable results.
- Consider non-linear relationships: If there are non-linear relationships between objectives, alternative methods such as fuzzy programming or goal programming with non-linear functions can be used to more accurately capture the complexity.
- Incorporate trade-offs: Instead of assigning fixed weights, allow decision makers to specify trade-offs between objectives. This can be achieved through techniques such as goal planning or compromise planning.
Overall, improvements to the weighted sum method involve adding more flexibility, capturing relationships between objectives, and reducing subjectivity in the assignment of weights.