Home | Linda's PhD Life
Beranda
Using Two-Population Genetic Algorithm to Support Deliberation Problem
Research in combinatorial optimization problems which deal with maximizing or minimizing a function of many variables subject to equality or inequality constraints have been done to find an optimal (or near optimal) solution. But for decision makers in real world, the optimal (or near optimal) solution is not enough. Before making a decision, they need additional information of the problem and the optimal solution. The additional information includes other alternative solutions and trade-off values between how much would be it worth to loosen the constraints and how much would it cost to tighten them. This additional information's needs creates a new problem that we call deliberation problem.
The deliberation problem is a problem that deals with providing the decision makers with useful information for making an informed decision for the underlying problem based on the model at hand. The deliberation problem also involves reconsideration of the combinatorial optimization problem itself. If the combinatorial optimization problem can be solved by finding one optimal (near-optimal) solution, deliberation problem for any combinatorial optimization problem gives more challenge.
In contrast with the combinatorial optimization problem, the deliberation problem has not received much attention from the research society. Although the deliberation problem would give great practical model to help the decision maker, but no approach has been introduced to support or solve that problem. For that reason, we were interested to develop an approach that supports the deliberation problem. More precisely, providing alternative solutions to support the deliberation problem.
To support deliberation problem, we need to find additional information in loosen and tighten the constraints. The simple approach to support this problem is to re-solve and re-compute the problem by additional loosen and tighten constraints. But most of the time, solving the original problem is already expensive, so re-solving and re-computing it often is not possible, even in a relative small search scale. Another reasonable approach is to solve the original problem with some form of population based approach that can give information and set of alternative solutions. With this approach, we don’t have to re-solve or re-compute the problem. Due to that reasoning, we propose two populations Genetic Algorithm (GA), as a variety of population based approach, to support deliberation. In our method, we use two populations GA that separate feasible and infeasible solutions. We call it Feasible-Infeasible Two Population Genetic Algorithm (FI2PopGA). We divide the populations and treat them differently. We implement FI2PopGA on a classical well-known NP-hard problem Generalized Assignment Problem (GAP).
The first version of our application was developed using MatLab. But due to some technical problems in MatLab, we have now developed our 2nd version in NetBeans (Desktop Application). Here is one screenshot from the application.
Contact:
School of Information System
Singapore Management
University
80 Stamford Road
Singapore 178902
Email:
lindawati.2008@phdis.smu.edu.sg