Högskolan i Skövde

Practitioners of multi-objective optimization currently lack open tools that provide decision support through knowledge discovery. There exist many software platforms for multi-objective optimization, but they often fall short of implementing methods for rigorous post-optimality analysis and knowledge discovery from the generated solutions. This paper presents Mimer, a multi-criteria decision support tool for solution exploration, preference elicitation, knowledge discovery, and knowledge visualization. Mimer is openly available as a web-based tool and uses state-of-the-art web-technologies based on WebAssembly to perform heavy computations on the client-side. Its features include multiple linked visualizations and input methods that enable the decision maker to interact with the solutions, knowledge discovery through interactive data mining and graph-based knowledge visualization. It also includes a complete Python programming interface for advanced data manipulation tasks that may be too specific for the graphical interface. Mimer is evaluated through a user study in which the participants are asked to perform representative tasks simulating practical analysis and decision making. The participants also complete a questionnaire about their experience and the features available in Mimer. The survey indicates that participants find Mimer useful for decision support. The participants also offered suggestions for enhancing some features and implementing new features to extend the capabilities of the tool.

In today’s uncertain and competitive market, where manufacturing enterprises are subjected to increasingly shortened product lifecycles and frequent volume changes, reconfigurable manufacturing system (RMS) applications play significant roles in the success of the manufacturing industry. Despite the advantages offered by RMSs, achieving high efficiency constitutes a challenging task for stakeholders and decision makers when they face the trade-off decisions inherent in these complex systems. This study addresses work task and resource allocations to workstations together with buffer capacity allocation in an RMS. The aim is to simultaneously maximize throughput and to minimize total buffer capacity under fluctuating production volumes and capacity changes while considering the stochastic behavior of the system. An enhanced simulation-based multi-objective optimization (SMO) approach with customized simulation and optimization components is proposed to address the abovementioned challenges. Apart from presenting the optimal solutions subject to volume and capacity changes, the proposed approach supports decision makers with knowledge discovery to further understand RMS design. In particular, this study presents a customized SMO approach combined with a novel flexible pattern mining method for optimizing an RMS and conducts post-optimal analyses. To this extent, this study demonstrates the benefits of applying SMO and knowledge discovery methods for fast decision support and production planning of an RMS.

In many practical applications, the end-goal of multi-objective optimization is to select an implementable solution that is close to the Pareto-optimal front while satisfying the decision maker’s preferences. The decision making process is challenging since it involves the manual consideration of all solutions. The field of multi-criteria decision making offers many methods that help the decision maker in this process. However, most methods only focus on analyzing the solutions’ objective values. A more informed decision generally requires the additional knowledge of how different preferences affect the variable values. One difficulty in realizing this is that while the preferences are often expressed in the objective space, the knowledge required to implement a preferred solution exists in the decision space. In this paper, we propose a decision support system that allows interactive knowledge discovery and knowledge visualization to support practitioners by simultaneously considering preferences in the objective space and their impact in the decision space. The knowledge discovery step can use either of two recently proposed data mining techniques for extracting decision rules that conform to given preferences, while the extracted knowledge is visualized via a novel graph-based approach that allows the discovery of important variables, their values and their interactions with other variables. The result is an intuitive and interactive decision support system that aids the entire decision making process — from solution visualization to knowledge visualization. We demonstrate the usefulness of this system on benchmark optimization problems up to 10 objectives and real-world problems with up to six objectives.

Multi-objective optimization involves the simultaneous optimization of several objective functions. In real-world problems, these objectives are often in conflict, giving rise to trade-offs in the optimal solutions from the optimization process. All these solutions are equally viable, with no single solution being better or worse than the others. Typically, decision makers have certain preferences that guide the selection of a final solution for practical implementation. While most multi-criteria decision analysis methods focus on the performance of solutions in the objective space, it is important to note that practically relevant knowledge is often found in the design space. Access to this knowledge can provide decision makers with meaningful insights into the problem and the optimization process, leading to more informed decision-making.

This thesis develops and employs methods for knowledge discovery in the context of multi-objective optimization. By emphasizing explicit knowledge representations, this thesis investigates how extracted knowledge can be processed and presented to decision-makers in an interactive manner for insightful decision support. This thesis also explores how extracted knowledge from preferred solutions can be integrated into the algorithms or the multi-objective optimization problem itself, to improve the convergence behavior of optimization algorithms. This approach, called Knowledge-Driven Optimization (KDO), can be implemented either offline or online. Offline KDO involves incorporating knowledge obtained from previous optimization runs into future problem scenarios of a similar nature, restricting the search process to preferred regions of the objective space. A main challenge with such approaches is the storage and retrieval of relevant past knowledge, as well as modifications to the optimization problem formulation. In contrast, online KDO involves integrating knowledge discovery methods with optimization algorithms and utilizing the knowledge obtained during their runtime to enhance the search process, driving algorithms towards better convergence in preferred regions of the objective space. This approach necessitates the development of new search operators capable of incorporating and exploiting various forms of knowledge.

In both offline and online KDO, the veracity and accuracy of the extracted knowledge are critical factors. The thesis validates the effectiveness of the developed methods using various benchmark and engineering optimization test problems, and use-cases from the manufacturing industry. A particular focus is given to generating explicit knowledge that is both meaningful to human decision makers, and can easily be processed algorithmically. The main contributions of this thesis are methods for discovering relevant knowledge about the convergence characteristics of problems, a decision support system for interactive knowledge discovery, and algorithms for realizing both offline and online KDO by incorporating knowledge into the optimization process.

Flermålsoptimering hanterar samtidig optimering av flera målfunktioner, vilka i praktiska optimeringsproblem ofta är i konflikt, vilket ger upphov till avvägningar i de optimala lösningarna från optimeringsprocessen. Alla dessa lösningar är lika värdefulla, och ingen lösning är bättre eller sämre än någon annan. Typiskt sett har beslutsfattare också preferenser som styr valet av en slutlig lösning att implementera i praktiken. De flesta metoder för analys av flera kriterier fokuserar på prestandan hos en uppsättning lösningar i målrymden, det är dock viktigt att notera att praktiskt relevant kunskap ofta finns i designrymden till lösningarna. Tillgång till denna kunskap kan ge beslutsfattare betydelsefulla insikter till både problemet och optimeringsprocessen, vilket leder till mer informerat beslutstagande.

Denna avhandling utvecklar och använder metoder för kunskapsutvinning i sammanhanget av flermålsoptimering. Genom ett särskilt fokus på explicit kunskap, undersöker denna avhandling hur utvunnen kunskap kan bearbetas och presenteras för beslutsfattare på ett interaktivt sätt för förbättrat beslutsstöd. Det undersöks också hur utvunnen kunskap från tidigare lösningar kan integreras i algoritmer för flermålsoptimerings eller direkt i optimeringsproblem för att avlasta beräkning av nya lösningar i optimeringsprocessen. Sådana metoder, kallade kunskapsdriven optimering (KDO), kan implementeras antingen offline eller online. Offline KDO innebär att integrera kunskap som erhållits från tidigare optimeringar, i framtida, liknande problem, vilket avlastar sökprocessen till preferensrika regioner i målrymden. En huvudsaklig utmaning med offline KDO är lagring och återhämtning av relevant tidigare kunskap, samt modifieringar av formuleringar till optimeringsproblem. I kontrast innefattar online KDO att integrera metoder för kunskapsutvinning tillsammans med optimeringsalgoritmer, och att utnyttja den resulterande kunskapen under optimeringen, för att förbättra sökprocessen och driva algoritmerna mot snabbare ankomst i preferensrika regioner i målrymden. Sådana metoder kräver utveckling av nya sökoperatorer kapabla att integrera och utnyttja olika former av utvunnen kunskap.

I både offline och online KDO är det viktigt att den integrerade kunskapen beskriver beslutfattarens preferenser noggrant. Denna avhandling validerar effektiviteten hos de utvecklade metoderna med hjälp av olika benchmark-optimeringsproblem, praktiska tekniska testproblem och fallstudier från tillverkningsindustrin. Ett särskilt fokus har lagts på utvinning av explicit kunskap som både är meningsfull för beslutsfattare och som enkelt kan bearbetas algoritmiskt. Denna avhandlings huvudsakliga bidrag består av metoder för utvinning av relevant kunskap om sökbeteendet för problem, ett beslutstödssystem för interaktiv kunskapsutvinning, samt algoritmer för att förverkliga både offline och online KDO genom att integrera kunskap i optimeringsprocessen.

Although an entire frontier of Pareto-optimal solutions exists for multi-objective optimization problems, in practice, decision makers are often only interested in a small subset of these solutions, called the region of interest. Specialized optimizers, such as reference-point based evolutionary algorithms, exist that can focus the search to only find solutions inside this region of interest. These algorithms typically only modify the selection mechanism of regular multi-objective optimizers to preferentially select solutions that conform to the reference point. However, a more effective search may be performed by additionally modifying the variation mechanism of the optimizers, namely the crossover and the mutation operators, to preferentially generate solutions conforming to the reference point. In this paper, we propose a modular mutation operator that uses a recent knowledge discovery technique to first find decision rules unique to the preferred solutions in each generation. These rules are then used to build an empirical distribution in the decision space that can be sampled to generate new mutated solutions which are more likely to be closer to the preferred solutions. The operator is modular in the sense that it can be used with any existing reference-point based evolutionary algorithm by simply replacing the mutation operator. We incorporate the proposed knowledge-driven mutation operator into three such algorithms, and through benchmark test problems up to 10 objectives, demonstrate that their performance improves significantly in the majority of cases according to two different performance indicators. 

Due to the nature of today's manufacturing industry, where enterprises are subjected to frequent changes and volatile markets, reconfigurable manufacturing systems (RMS) are crucial when addressing ramp-up and ramp-down scenarios derived from, among other challenges, increasingly shortened product lifecycles. Applying simulation-based optimization techniques to their designs under different production volume scenarios has become valuable when RMS becomes more complex. Apart from proposing the optimal solutions subject to various production volume changes, decision-makers can extract propositional knowledge to better understand the RMS design and support their decision-making through a knowledge discovery method by combining simulation-based optimization and data mining techniques. In particular, this study applies a novel flexible pattern mining algorithm to conduct post-optimality analysis on multi-dimensional, multi-objective optimization datasets from an industrial-inspired application to discover the rules regarding how the tasks are assigned to the workstations constitute reasonable solutions for scalable RMS. 

Usually, optimizing productivity and optimizing worker well-being are separate tasks performed by engineers with different roles and goals using different tools. This results in a silo effect which can lead to a slow development process and suboptimal solutions, with one of the objectives, either productivity or worker well-being, being given precedence. Moreover, studies often focus on finding the best solutions for a particular use case, and once solutions have been identified and one has been implemented, the engineers move on to analyzing the next use case. However, the knowledge obtained from previous use cases could be used to find rules of thumb for similar use cases without needing to perform new optimizations. In this study, we employed the use of data mining methods to obtain knowledge from a real-world optimization dataset of multi-objective optimizations of worker well-being and productivity with the aim to identify actionable insights for the current and future optimization cases. Using different analysis and data mining methods on the database revealed rules, as well as the relative importance of the design variables of a workstation. The generated rules have been used to identify measures to improve the welding gun workstation design.

Current market requirements force manufacturing companies to face production changes more often than ever before. Reconfigurable manufacturing systems (RMS) are considered a key enabler in today's manufacturing industry to cope with such dynamic and volatile markets. The literature confirms that the use of simulation-based multi-objective optimization offers a promising approach that leads to improvements in RMS. However, due to the dynamic behavior of real-world RMS, applying conventional optimization approaches can be very time-consuming, specifically when there is no general knowledge about the quality of solutions. Meanwhile, Pareto-optimal solutions may share some common design principles that can be discovered with data mining and machine learning methods and exploited by the optimization. In this study, the authors investigate a novel knowledge-driven optimization (KDO) approach to speed up the convergence in RMS applications. This approach generates generalized knowledge from previous scenarios, which is then applied to improve the efficiency of the optimization of new scenarios. This study applied the proposed approach to a multi-part flow line RMS that considers scalable capacities while addressing the tasks assignment to workstations and the buffer allocation problems. The results demonstrate how a KDO approach leads to convergence rate improvements in a real-world RMS case.

This paper compares the performance of the classic genetic algorithm with the more recently proposed ant colony optimisation for solving real-world pickup and delivery problems with hard time windows. A real-world problem that is present worldwide – waste collection – is used to evaluate the algorithms. As in most real-world waste collection problems, many of the waste bins have time windows. The time windows stem from such things as safety regulations and customer agreements, and must be strictly adhered to. The optimisation showed that the genetic algorithm is better than the ant colony optimisation when utilising standard implementations of both algorithms. However, when the algorithms are enhanced with a local search procedure, the ant colony optimisation immediately becomes superior and achieves improved results. Local search seems to be a drawback for the genetic algorithm when hard time windows are involved. Various implementations of the local search procedure are evaluated in this paper using five different test sets. Recommendations for future implementations are given as well as additional enhancements which could improve the performance of the ant colony optimisation. 

The use of evolutionary algorithms for solving multi-objective optimization problems leaves the decision makers with a set of Pareto-optimal solutions to be considered in their decision making. Multi-objective optimization problems offer two spaces for a decision maker to analyze, the decision space and the objective space. In the literature, most of the focus has been on analyzing the objective space, however, in this paper, two procedures are presented for analyzing the decision space by identifying the variables that predominantly influence the structure of the objective space. Both procedures employ a recently proposed rule mining approach, which is used to find significant rules in terms of the variables. The rules are then combined and an influence score is calculated. The method is demonstrated on four problems, two scalable test problems (DTLZ2 and WFG2) with cases of three, five and seven objectives, one engineering design problem and one simulation-based optimization problem. The experiments show that the proposed approach is able to identify influential variables in most problem cases.