ABSTRACT

A multi-objective optimization problem has two or more objectives to be minimized or maximized simultaneously. It is usually difficult to arrive at a solution that optimizes every objective. Therefore, the best way of dealing with the problem is to obtain a set of good solutions for the decision maker to select the one that best serves his/her interest. In this paper, a ratio min-max strategy is incorporated (after Pareto optimal solutions are obtained) under a weighted sum scalarization of the objectives to aid the process of identifying a best compromise solution. The bi-objective discrete optimization problem which has distance and social cost (in rail construction, say) as the criteria was solved by an improved Ant Colony System algorithm developed by the authors. The model and methodology were applied to hypothetical networks of fourteen nodes and twenty edges, and another with twenty nodes and ninety-seven edges as test cases. Pareto optimal solutions and their maximum margins of error were obtained for the problems to assist in decision making. The proposed model and method is user-friendly and provides the decision maker with information on the quality of each of the Pareto optimal solutions obtained, thus facilitating decision making.

Keywords:

Optimization, Discrete, Bi-Objective, Ratio Min-Max, Network, Pareto Optimal

1. Introduction

Optimization is defined as a process for finding the best solution to a problem, referred to as the global optimal solution from a given set of possible (feasible) solutions [1] . Applications of optimization are found in Engineering, Science, Economics, Finance, Medicine and Mathematics [1] .

In today’s business environment, where cost of production is high coupled with a lot of competitions due to globalization, single-objective optimization problems have become less popular. Much attention has now been shifted to multi-objective optimization problems. A multi-objective optimization problem has a set of objectives that are usually in competition or conflict; the appreciation of one objective results in the depreciation of the other [2] . It is very difficult or impossible to obtain a solution that is optimal for each of the objectives. The best way is to find a solution that will be adjudged the best compromise one.

The aim of this paper is to develop a model and methodology that will generate a set of Pareto solutions and also a way to assist the decision maker to choose the best compromise solution. The next section outlines the multi-objective optimization model and solution methods, with specific focus on the normed and weighted sum; solution algorithms are also given some general attention with a special one for the Ant Colony System algorithm, which the authors have made some improvements to [3] . A weighted sum ratio min-max strategy is proposed in the next section followed by the consideration of some test cases to generate numerical results in the subsequent section. The results are discussed in the succeeding section, while the last concludes the paper.

2. Methodology

2.1. Multi-Objective Optimization

Multi-objective optimization is concerned with minimizing or maximizing more than one objective function at the same time, subject to some constraints [4] . A general mathematical model of multi-objective optimization is given as:

$\min \left\{f_1\left(x\right),f_2\left(x\right),\cdots ,f_n\left(x\right)\right\}$

subject to $g_i\left(x\right)\le b_i,i=1,2,\cdots ,m$ (1)

where $x\in X$ is a vector of decision variables, $f_j$ is the jth objective function $\left(j=1,2,\cdots ,n\right)$ , $g_i$ is the constraint function $\left(i=1,2,\cdots ,m\right)$ , and $b_i$ is the limit on the ith constraint. The expression (1) is nonlinear if at least one objective function or constraint is nonlinear, otherwise it is linear. It is continuous if the decision variables can assume continuous values. It is discrete if the decision variables can only assume discrete values, and mixed if both continuous and discrete values are admissible; in the last two cases, additional notation to those effects are included in (1).

2.2. Concept of Optimality

The problem defined in (1) belongs to the class of constrained multi-objective optimization problems, within this class of problems there are the linear types, the nonlinear types, the continuous types, the discrete and the mixed integer types [5] . Generally, there is no unique minimum, but rather a set of equally good solutions [6] . Notable notions of optimality are: Pareto, min-max, and lexicographic, with the most fundamental of these being Pareto optimality which is derived from the concept of dominance. Therefore, Pareto optimality can also be called Pareto dominance.

A decision vector $x^{*}\in X$ is said to dominate a decision vector $x\in X$ or is Pareto optimal, if $f_i\left(x^{*}\right)\le f_i\left(x\right)$ for all $i=1,2,\cdots ,n$ and if $f_j\left(x\right)\le f_j\left(x\right)$ for some $j\in \left\{1,2,\cdots ,n\right\}$ . For a fuller discussion of the subject the reader is referred to [6] [7] . This definition indicates that there is more than just one solution that is Pareto optimal. There could be many or even infinite solutions, depending on the type and nature of the problem [8] [9] . The question of which is the most acceptable solution is subjective, and the final solution of the decision maker is always based on a trade-off between objectives. Even so, obtaining a Pareto optimal solution set is preferable to having just a single solution, due to its practicability to real-life problems.

2.3. Solution Methods

There are a number of methods designed to assist the decision maker to arrive at the best compromise solution. The most classical of the methods use a number of schemes to convert the multiple objectives into a scalar one [10] [11] (these would be the focus of our discussions in this paper) and apply standard scalar optimization algorithms which generate one Pareto optimal solution with each run of the algorithm [12] . The unique optimum which results as solution is considered Pareto optimal under certain conditions required by the particular method. There are algorithms today, such as the meta-heuristic ones however, that can generate portions or the entire Pareto optimal solutions in a single run of the algorithm due to their global search approach to finding solutions. One of such algorithms is the Ant Colony algorithm, which is the choice algorithm in this work due to its suitability as observed in the next section. Obtaining a Pareto optimal solution set is preferable to a single solution, since it provides a basis upon which to make value judgment’s in order to settle on a final solution.

An important attribute of the methods under the classical class is that of using them interactively by incorporating user preferences directly into the algorithm at specified stages of the solution process, such as before, during, or after the run of the algorithm [13] [14] in order to find the user’s best compromise solution. This means that it may not be necessary to produce the entire Pareto optimal solution set where the user’s preference is available. There is the risk, however, of obtaining a solution that is not Pareto optimal with this approach [15] . In this section attention is devoted to two of the methods in view of the fact that they are related to this work; these are the Global Criterion (or the Normed) and weighted sum methods.

The normed method, also called compromise programming, global criterion, or utopian point method [14] [16] minimizes the aggregate relative distance from a prospective solution to the actual optimal solution of the objective [17] . The method is defined as:

$\min {\left|{\displaystyle \sum }_{j=1}^n{\left|\frac{f_j-f_j^{*}}{f_j^{*}}\right|}^p\right|}^{\frac{1}{p}},x\in X,1\le p\le \infty$ (2)

where $f_j^{*},j=1,2,\cdots ,n$ is the unique value of the jth objective function, and the utopian solutions are given by the vector ${\left(f_1^{*},f_2^{*},\cdots ,f_n^{*}\right)}^{\text{T}}$ [18] . A utopia solution is a vector of the unique solutions of the individual objectives and is generally infeasible. The power p offers the various ways of calculating the relative distance. The most often used values of p are 1, 2 and ∞. When ∞ is assigned, the resulting scalar problem is called min-max optimization as defined by [16] . Pareto optimal solutions are obtained by incorporating weights in (2) and the weighted sum approach used to find the Pareto optimal solutions.

The Weighted-Sum method: Since the development of the concept of Pareto optimality in Economics by Vilfredo Pareto in 1906 and the application of it in Engineering and Science by Stadler in the 1970s [19] , the weighted sum method has been the most commonly used in solving a multi-objective optimization problem. The objective functions are weighted and aggregate in a single objective function as in (3):

$\min F\left(x\right)={\displaystyle \sum }_{i=1}^n{w}_j{f}_j(\; x\; )$

subject to $x\in X,{\displaystyle {\sum }_{j=1}^n{w}_i}=1,w_j\ge 0,\forall j$ (3)

where $w_j$ is the weight of the j^th objective function [20] . The weights are assigned to the objectives by the decision maker or analyst. The weights indicate the relative importance of the objective functions to the user. Each set of weights used results in a single optimal solution [21] . For fuller and more detailed discussion of the existing methods of solution of the problem in (1) the reader is referred to [14] .

Since in general the objective functions in a given problem may be dimensionally unequal, and to avoid ambiguity in the weights that are assigned to the objective functions, the objective functions may be normalized (i.e., the value of each of objective function is mapped onto the interval [0 1]). For specific examples the reader is referred to [22] [23] .

3. Bi-Objective Problem

Let $G\left(V,E\right)$ be an undirected graph consisting of an indexed set of nodes V with $n=\left|V\right|$ and a spanning set of edges (arcs) E with $m=\left|E\right|$ , where n and m are the number of nodes and edges (arcs) respectively. Each arc is represented as a pair of nodes, thus from node i to node j, and denoted by $\left(i,j\right)$ . Let each arc be associated with two numbers: the distance $d_{ij}$ and social cost $A_{ij}$ in constructing rail lines to link nodes (towns) and let the arcs represent the streets.

The bi-objective optimization problem is thus:

$\min f_1\left(p\right)={\displaystyle \sum }_{\left(i,j\right)\in E}{d}_{ij}{x}_{ij}$

$\min f_2\left(p\right)={\displaystyle \sum }_{\left(i,j\right)\in E}{A}_{ij}{x}_{ij}$

subject to $x_{ij}\in \left\{0,1\right\},\forall \left(i,j\right)\in E,i=1,2,\cdots ,n-1$ and $j=1,2,\cdots ,n$ (4)

where $x_{ij}$ is the decision variables for selecting or otherwise, nodes $\left(i,j\right)$ , p is the path from the source to the destination, $f_1$ and $f_2$ respectively the distance function and social cost function with $f\left(p\right)=\left(f_1,f_2\right)$ . The problem (4) belongs to the class of discrete multi-objective optimization. The techniques for solving continuous multi-objective optimization problems are also application to this type of problem as given in (4), however, there are some limitations on the ability of the methods to find the entire Pareo optimal solutions [24] . The computational challenges for such problems are also similar to those encountered in continuous problems in the application of any scalar methods.

It must be observed that in this problem (4), the objectives are not inherently in conflict and that the conflict could only arise in the data which may be used. For example, the possibility of both the distance and social cost decreasing at the same time and vice versa is real. Therefore there is the possibility of obtaining a unique optimal solution.

Solution Technique

The weighted sum is applied as the solution method to obtain Pareto optimal solutions, following which a post-optimality ratio min-max strategy is employed as an aid in the process of identifying a best compromise solution for the decision maker. Suppose K is the set of Pareto optimal solutions, such that $p\in K$ is a Pareto optimal path, then the proposed ratio min-max strategy is given by:

$\min \left\{F\left(p,w\right)\right\}=\min \left\{\max \left|\frac{F_j^{*}\left(p,w\right)}{f_j^{*}\left(p\right)}-1\right|,\forall j:p\in K\right\}$

where $f_j^{*}\left(p\right)$ is the unique optimal solution value of j^th objective function, $F_j^{*}\left(p,w\right)$ is the value of the j^th objective function at a Pareto optimal solution after the weighted sum optimization, $F\left(p,w\right)$ is therefore a measure of the maximum margin of error of the j^th objective function at the Pareto optimal solutions.

The following steps depict the process towards finding the best compromise solution:

Step 1: Compute $f_j^{*}\left(p\right)$ , the unique optimal value of the j^th objective function for all $p\in K$ ;

Step 2: Perform the weighted sum optimization with a set of generated weights;

Step 3: Compute $F_j^{*}\left(p,w\right)$ , the value of the j^th objective function for all $p\in K$ ;

Step 4: Compute the absolute values of the ratios $F_j^{*}\left(p,w\right)$ to $f_j^{*}\left(p\right)$ less than one #Math_48# and $p\in K$ ;

Step 5: Select the maximum values of the result in Step 4 $\forall j$ and $p\in K$ ;

Step 6: Choose the minimum value in step 5.

The proposed strategy finds the margin of errors of the Pareto optimal of the objective functions values relative to their utopian ones to assists the decision maker to choose the result which best suits his/her interest.

4. Solution Algorithm

The Ant Colony algorithm is in the class of meta-heuristic algorithms and was primarily designed to handle network problems. It has demonstrated its ability to obtain the best solution for large and combinatorial optimization problems [25] [26] and it is also flexible. The development of the Ant Colony Optimization (ACO) meta-heuristic algorithm was inspired by the socialist lifestyle exhibited by ants in search of food and other provisions [27] [28] . Individual ants are considered un-intelligent and are practically blind and crappy in sight. But with their social structure, they are able to determine the shortest path to a food source after discovering it [29] .

Ants, in the course of looking for food and other provisions, drop a chemical called pheromone in their trail anytime they come across food to attract other ants to the place [30] . So the ants that move along the shortest path accommodate more amounts of pheromones per unit length. The amount of pheromone that an ant deposit is inversely proportional to the distance travelled. That is the higher the density of pheromone the shorter the path [30] [31] .

The Ant Colony algorithm uses the decision of the artificial ants to move from node to node by a stochastic process which is dictated by the magnitude of the pheromone on the route.

There are three main kinds of Ant Colony Optimization algorithms: 1) the Ant System (AS) by [32] , 2) the Max-Min Ant System (MMAS) by [33] and 3) the Ant Colony System (ACS) by [34] as cited in [35] . The contributions of the authors are with respect to the third. The specific improvements made to the algorithm are discussed next.

An Improved Ant Colony System Algorithm

The ACS algorithm involves seven main steps, which are: 1) setting parameters, 2) initializing pheromone trails, 3) calculating the heuristic Information, 4) building the ant solution by using the stochastic state transition rule, 5) updating the local pheromone, 6) applying local search to improve solution constructed by an ant, and 7) updating the global pheromone information. The contributions of the Authors [3] are in (2), (3) and (4). The modifications mode in these three specific areas of the ACS—a detailed discussion of which are presented in [3] , results in improvement of the ACS algorithm, in terms of the number of iterations required for convergence. The proposed modifications are presented here as follows:

The initial pheromone ${\tau }_{ij}\left(0\right)$ that is deposited along $\left(i,j\right)$ at the beginning of the search, which is usually a small positive constant, is proposed:

${\tau }_{ij}\left(0\right)=\frac{1}{\left(n-1\right){\overline{L}}_{ij}}$

where n is the number of nodes (i.e., the problem size), ${\overline{L}}_{ij}$ is the ratio of the weighted sum of the distance and social cost linking node i to node j to the total from the source node to the current node.

The heuristic information in literature is calculated from the current node, i where the ant is to the next node j. This approach, however, fails to provide the ant with information on the nature of the path from source node to the current node i. This shortcoming is addressed in the reformulation. The heuristic information is calculated from the source node to the present node i and from node i to the next node j as:

${\eta }_{ij}=w_1{\eta }_{0j}^1+w_2{\eta }_{0j}^2$

${\eta }_{0j}^1=\frac{1}{\left(d_{0i}+d_{ij}\right)}\text{and}{\eta }_{0j}^2=\frac{1}{\left(A_{0i}+A_{ij}\right)}$

$w_1,w_2\in w$ and $0\le w\le 1$ ,

where $d_{0i}$ is the total distance from the source node to the present node i, $A_{0i}$ is the total social cost from the source node to the present node i.

The aim of local pheromone update is to reduce the content of the pheromone along the routes to encourage other ants to generate new paths. The practice has been to deduct a constant amount along all routes. Even so, care needs to be taken to ensure that paths far from optimal are not created. To address this, the local pheromone update model is reformulated to ensure that reduction in the pheromone levels during the construction of paths is done in such a way that smaller amounts are taken from the shorter routes compared to the longer ones. The proposed ratio approach is:

${\tau }_{ij}\left(t+1\right)=\left(1-\rho \right)\frac{{\tau }_{ij}\left(t\right)}{L_{ij}}+\rho {\tau }_{ij}\left(0\right),$

where $L_{ij}={\displaystyle \sum {\tau }_{ij}\left(t\right)}$ and $\rho$ is the rate of evaporation of the pheromone.

Also, to speed up the process of arriving at the optimal solution, a new approach is proposed to calculate the pheromone increment. This is the global pheromone update, which is modeled as:

${\tau }_{ij}\left(t+1\right)=\left(1-\rho \right){\tau }_{ij}\left(t\right)+\frac{1}{\rho }{\displaystyle \sum _{k=1}^m\Delta {\tau }_{ij}^k}$

$\Delta {\tau }_{ij}^k=\{\begin{array}{l}\frac{1}{\overline{L}}\cdot \frac{L^k-L_{ij}}{L^k},\text{if}\left(i,j\right)\in U_i\text{or}{I}_i\\ 0,\text{otherwise}\end{array}$

where $L_{ij}$ is the weighted sum of distance and social cost $\left(w_1{d}_{ij}+w_2{A}_{ij}\right)$ of the edge $\left(i,j\right)$ , $L^k$ is weighted sum of distance and social cost of the kth solution generated by ant k, $\overline{L}$ is the ratio of the weighted sum of the two criteria of the solutions.

In constructing the feasible solutions, the decision by the ants to move from one node to the next is based on a stochastic probability rule. The proposed initial pheromone trail, heuristic information, local pheromone update and global pheromone trail update are embedded in the expression below, as in [36] :

$P_{ij}^k\left(t\right)=\{\begin{array}{l}1\text{if}q\le q_0\text{and}j=j^{*}\\ 0\text{if}q\le q_0\text{and}j\ne j^{*}\\ \frac{{\left({\tau }_{ij}\left(t\right)\right)}^{\alpha }{\left({\eta }_{ij}\left(t\right)\right)}^{\beta }}{{{\displaystyle \sum }}_{r\in N_i^k}{\left({\tau }_{ir}\left(t\right)\right)}^{\alpha }{\left({\eta }_{ir}\left(t\right)\right)}^{\beta }}\text{otherwise}\end{array}$

$j^{*}:\text{yields}\arg {\max }_{r\in N_i^k}\left({\left({\tau }_{ij}\left(t\right)\right)}^{\alpha }{\left({\eta }_{ij}\left(t\right)\right)}^{\beta }\right)$ and it is used to identify the unvisited node in $N_i$ that maximizes $P_{ij}^k\left(t\right)$ .

$N_i^k\in N_i$ is the set of nodes which are the neighbors of node i and are not yet visited by ant k (nodes in $N_i^k$ are obtained from those in $N_i$ by the use of ant k’s private memory $H_i^k$ (which stores nodes already visited by the ant)). $N_i$ is the set of nodes which are directly linked to node i by an edge (i.e. the neighbours of node i). ${\tau }_{ij}\left(t\right)$ is the quantity of pheromone trail laid along the edge linking node i and node j. ${\eta }_{ij}\left(t\right)$ is the heuristic information for the ant visibility measure. $\alpha$ is the parameter to control the influence of ${\tau }_{ij}$ . $\beta$ is the parameter to control the influence of ${\eta }_{ij}{q}_0$ is the pre-defined parameter ( $0\le q_0\le 1$ ). q is the uniformly distributed random number to determine the relative importance of exploitation versus exploration, $q\in \left[0,1\right]$ .

5. Numerical Test Cases

Two example networks are presented and their results discussed in this section.

5.1. Test Case 1

The first network has fourteen (14) nodes and twenty-eight (28) edges with the node labeled 1 being the source and the one labeled 14 being the destination (see Figure 1). The aim is to find a path from 1 to 14 which minimizes the distance and the social cost simultaneously.

In Table 1, the first and second columns are the names of the paths and their composites (path sets). The third column gives the values of the weights. The fourth column gives the Pareto optimal objective function values and the fifth gives the min-max ratio values. The sixth column gives the margin of error (ME) and the seventh the maximum margin of error (MME) values. The eighth and the ninth columns give the number of iterations that the existing ACS (E) and the Improved ACS algorithms (I) each takes to converge to the optimal solution [3] . The last row gives the utopia solution of each of the objective functions.

The first row of Table 1 shows that the path 1-4-8-10-13-14 yields a minimum distance of 14 km and a minimum social cost of 11 units; the min-max ratios for the distance and social cost values are approximated to 1.17 and 1.47 respectively, leading to a margin of error 0.17 and 0.47 respectively and hence a maximum margin of error of approximately 0.47. The margin of error and the maximum margin of error (MME) figures show that whereas the minimum distance was 17% short of the ideal solution for distance, the minimum social cost value was 47% short of the ideal solution. The new algorithm has less number of iterations compared to the existing one, which is an improvement over the existing one. Similar interpretations apply to the rest of the rows of the table.

The results support the view expressed above that, the multi-objective optimization model is such that the objectives are not inherently in conflict and that the conflict could only arise in the data itself. This is evidenced by the objective function values of (12, 7) obtained. The values are clearly the same as the utopian ones (see last row of the table). This indicates that the objectives are not in conflict for most of the data used in this network. The objective function values of (12, 7) dominate all the others in the table, except (12, 10) which it weakly dominates. This observation explains the optimal objective function values, margin of error and maximum margin of error values obtained in Table 1. The unique solution therefore is (12, 7) with the shortest path being (1-4-7-11-12-14).

The other solutions which are dominated by the unique solution (as seen in Table 1) may be worth considering, however, by a decision maker if the problem was with a time window constraint (the need for alternative routes to cater for traffic during the day and other unforeseen problems), for instance, or with other similar conditions. The time window constraint may arise when the distance and the social cost values are worse than the optimal but they offer a better time window.

5.2. Test Case 2

This consists of a larger network of twenty (20) nodes (from 1 as source to 20 as destination) as shown in Figure 2. Interpretations of this figure are similar to that of Test Case 1.

The first row of Table 2 shows that the path 1-2-8-16-20 yields a minimum distance of 16 units and a minimum social cost of 11 units; the min-max

ratio values for the distance and cost are approximated to 1.33 and 1.22 respectively leading to a margin of error of 0.33 and 0.22 respectively and hence a maximum margin of error of approximately 0.33. The margin of error and the maximum margin of error (MME) figures show that whereas the minimum distance was 33% short of the ideal solution for distance, the minimum social cost value was 22% short of the ideal solution. Similar interpretations are applied to rest of the table.

The results confirm the notion in literature that in the weighted sum method, variation of weights does not necessarily result in different solutions. Also, the size of the Pareto optimal solution set does not depend on the size of the network. Moreover, the problem associated with the new method is that, different paths (solutions) may have the same maximum margin of error but may not have the same objective function values (as in path $p_7$ and path $p_8$ in Table 2). Finally, the zero maximum margin of error obtained in Case 1 signifies that, the solution obtained is the best for the two objectives.

6. Conclusion

A ratio min-max strategy to help a decision maker identify a best compromise solution in a bi-objective discrete optimization function and solved by the weighted sum method has been proposed. The problem was illustrated in the context of finding the shortest distance and least social cost in hypothetical rail construction to link a source and destination. An improved ant colony system algorithm was used to find solutions for two hypothetical network problems. The proposed method is user-friendly and also provides the decision maker with the quality of each of the Pareto optimal solutions obtained, making it easy to identify the best compromise solution. A future direction would be to apply the model and methodology to a real network.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

Cite this paper

Kparib, D.Y., Twum, S.B. and Boah, D.K. (2019) A Min-Max Strategy to Aid Decision Making in a Bi-Objective Discrete Optimization Problem Using an Improved Ant Colony Algorithm. American Journal of Operations Research, 9, 161-174. https://doi.org/10.4236/ajor.2019.94010

References