هیبریداسیون از شبکه های بیزی و الگوریتم های تکاملی برای بهینه سازی چند هدفه در طراحی محصول و مدیریت پروژه زمینه یکپارچه

A better integration of preliminary product design and project management processes at early steps of system design is nowadays a key industrial issue. Therefore, the aim is to make firms evolve from classical sequential approach (first product design the project design and management) to new integrated approaches. In this paper, a model for integrated product/project optimization is first proposed which allows taking into account simultaneously decisions coming from the product and project managers. However, the resulting model has an important underlying complexity, and a multi-objective optimization technique is required to provide managers with appropriate scenarios in a reasonable amount of time. The proposed approach is based on an original evolutionary algorithm called evolutionary algorithm oriented by knowledge (EAOK). This algorithm is based on the interaction between an adapted evolutionary algorithm and a model of knowledge (MoK) used for giving relevant orientations during the search process. The evolutionary operators of the EA are modified in order to take into account these orientations. The MoK is based on the Bayesian Network formalism and is built both from expert knowledge and from individuals generated by the EA. A learning process permits to update probabilities of the BN from a set of selected individuals. At each cycle of the EA, probabilities contained into the MoK are used to give some bias to the new evolutionary operators. This method ensures both a faster and effective optimization, but it also provides the decision maker with a graphic and interactive model of knowledge linked to the studied project. An experimental platform has been developed to experiment the algorithm and a large campaign of tests permits to compare different strategies as well as the benefits of this novel approach in comparison with a classical EA.

Many companies, in order to meet the requirements of their clients and to provide them with adequate products, implement two key processes: – the “product design” process, which aims at defining precisely the components and the structure of the product, – the “project design” process which aims at specifying how the product will be realized (sequence of tasks, used resources…). These two processes are often implemented sequentially: first the product is designed then the realization project is elaborated. For example, when a client wants to build a house, the architect designs at first a plan of the house, then the corresponding realization project is developed and launched. Since the project constraints (for example resources availability) are not explicitly taken into account in the product design, this can lead to additional iterations between “product design” and “project design” processes. A better integration (or coupling) of both processes is therefore a way to improve the global performance of companies. An in-depth study of several mechanisms that can facilitate this integration has been launched in a project called ATLAS, funded by the French National Research Agency and involving academic laboratories, industrialists and the competitiveness cluster Aerospace Valley. The work presented in this paper takes place in the context of the ATLAS project. In this section, a simplified product/project integration model is proposed. Indeed, in both environments (product and project), design processes are generally achieved according to a hierarchical decomposition (see Fig. 1) in order to encompass complexity: – products are recursively decomposed into smaller sub-products (“AND” connectors), e.g. product P1 is made of P11 and P12, – accordingly, projects are recursively decomposed into sub-projects: in order to realize P1 one has to realize P11, to realize P12 and to assemble P11 and P12, – alternatives (“XOR” connectors) can be defined in products (e.g. choice between components P11 is composed of View the MathML sourceP11′ XOR View the MathML sourceP12″) and in projects (e.g. choice between sub-contractors View the MathML sourceR7′ XOR View the MathML sourceR7″ to achieve task T7). Definition 1. an integrated model, called project graph, is used in order to represent simultaneously the links between the product and project hierarchies. This model consists in an oriented graph without cycles in which nodes are: tasks of the project, “AND” connectors and “XOR” connectors. The oriented arcs represent the precedence constraints between tasks. Fig. 2 represents such a model for the example of decomposition given in Fig. 1. Such a graph permits to capitalize that is called “structural knowledge” in the rest of the article. It concerns XOR nodes that correspond to the possible choices of products’ structure. Making a product choice corresponding to a XOR node imply to inhibit a set of downstream connected nodes. Those product XOR are represented by a circular node whereas project XOR, which do not involve inhibition of other XOR node, are represented by dotted circle. Full-size image (14 K) Fig. 2. Example of integrated model: the project graph. Figure options Definition 2. a scenario corresponds to a graph in which all the choices are made (i.e. with no more XOR nodes). An example of scenario, corresponding to the model in Fig. 2, is illustrated in Fig. 3. Full-size image (9 K) Fig. 3. Example of scenario s. Figure options Full-size image (33 K) Fig. 1. Example of product/project decomposition. Figure options 1.1. Mathematical description of the addressed problem: The problem addressed in this paper consists in searching an optimal scenario among all the possible ones within the simple directed graph project. The project graph G=(α, β) is defined by: α={αk}, the set of all nodes, β={βij}, the set of directed edges between the node αi and the node αj with |β| the total number of edges. The following subsets permit to formalize the problem defining the three different node types (XOR, AND, Task): T={αp/αp is a task node, αp∈α} is the subset of task nodes with |T| the total number of task nodes, XOR={αq/αq is a XOR node, αq∈α} is the subset of XOR nodes with |XOR| the total number of XOR nodes, AND={αr/αr is an AND node, αr∈α} is the subset of AND nodes with |AND| the total number of AND nodes. Let X, the vector of discrete variables (decision variables) corresponding to XOR nodes equation(1) X={xi/αi∈XOR}X={xi/αi∈XOR} Turn MathJax on Let Dxi, the domain of the variable xi defined by the vector of identifiers of the direct successor nodes of the XOR node i. equation(2) View the MathML sourceDxi={j/αj∈α,βij∈β,αi∈XOR} Turn MathJax on A decision associated to a XOR node αk that participates to a scenario s corresponds to the instantiation of the variable xk and is defined by equation(3) View the MathML sourcexks=jwithj∈Dxk Turn MathJax on Let Xs, the vector of instantiations of all the variables corresponding to the scenario s equation(4) View the MathML sourceXs={xks/αk∈XOR} Turn MathJax on Let Gs(Xs) the directed graph obtained by instantiation of all the variables and corresponding to the scenario s (e.g. see Fig. 2). Gs(Xs)=(αs, βs). αs is the set of nodes belonging to the scenario s and βs, the set of edges. Gs depends on the variables instantiation Xs. Let fm(xs), the value of the criteria m for the scenario s that depends on the variables instantiation Xs. This value is computed from the graph Gs(Xs) and depends on the considered criteria m. For instance, if the criteria m is the cost, fm(Xs) is equal to the sum of all the elementary task costs. If the criteria m is the delay, it is necessary to find the longest path in the graph Gs and then, fm(Xs) represents the final delay of the scenario. Therefore, considering a scenario s, each criteria m is evaluated in a specific manner using an appropriate algorithm to apply to the graph Gs. Let fm(X), the objective function to optimize corresponding to the criteria m and depending on the variables X. Considering that there is P objective functions to optimize, the multi-valuated optimization function f is defined by equation(5) View the MathML sourceminf(X)=min(f1(X),f2(X),...,fP(X)) Turn MathJax on This problem can be considered as an extended product configuration optimization problem. The existing literature on the subject is mainly dedicated to finding a feasible configuration according to constraints and knowledge on the domain. However, as mentioned in Li et al. (2006) it is very difficult to optimize the resulting configured product since a problem of combinatorial explosion appears especially when the problem is loosely constrained. In this case, using an optimization approach can help to focus on good solutions. In Baron et al. (2004) a search method, based on a classical multi-objective evolutionary algorithm, was proposed for the problem of scenario selection with promising results. The method proposed in Baron et al. (2004) is improved by taking into account the knowledge that can be capitalized from previous optimizations (learning from experience). Another important issue is to make the capitalized knowledge explicitly available to the decision maker and, therefore, to help him understand the proposed solutions. This enables to avoid the black-box effect of a combined simulation-optimization approach without knowledge acquisition. The main idea developed in this paper is to guide the search process with the available knowledge and, reciprocally, to improve the knowledge by learning from the most interesting solutions obtained during search. The background of this work, with respect to existing approaches that mix learning and search, is given in Section 2. Then, the proposed approach, based on a hybridization between bayesian networks (for knowledge acquisition) and evolutionary algorithms (for search) is described in Section 3. Finally, the results obtained on the target problem are discussed in Section 4.

This paper is focused on the description and evaluation of a new evolutionary algorithm for the selection of project scenarios in the early phases of a system design. The underlying problem is highly combinatorial especially when decisions on the product and on the project are integrated in a single model, called project graph. In order to benefit from expert knowledge and from past optimizations, a hybridation between a learning algorithm and a search algorithm is proposed. A model of knowledge, used to capitalize the knowledge that links decisions, environment, objectives and concepts, is defined using the Bayesian network formalism. This model is obtained from experts and from a learning process using some solutions generated by the EA. This model is used in order to give orientations to the EA to reach a priori interesting zones of the multi-objective space. In a decision aided perspective, the guided search process has to give some solutions well distributed on the Pareto front. The proposed method is based on the hybridation of a classical strength Pareto evolutionary algorithm in order to guide the search process by means of the model of knowledge. New operators of initialisation, crossover and mutation are defined. Their behaviour is oriented by probabilities contained into the MoK. Since the MoK can be incomplete or erroneous, a MoK updating process based on in-line learning permits to make it evolve during optimization. Obtained results show the interest of the different levels of knowledge reuse for orientation of an evolutionary algorithm. When the knowledge contained in the model of knowledge is reliable, the proposed method allows a significant improvement of performance. When the MoK is erroneous or incomplete, the tests realised on learning algorithm enabled us to study the learning process abilities with the suggested method. To validate our approach completely, it still remains to confront it with standard problems (“benchmarks”). However, tests carried out show the high performances of the evolutionary algorithm oriented by knowledge compared to a traditional EA. Moreover, the advantages of the proposed model relate not only to a well guided and more efficient optimization than with classical EA, but also to the possibility to capitalize knowledge about previously planned projects according to their context, and to provide decision makers with the MoK used during optimization in addition to the optimized solutions. It is indeed useful for decision makers to use the Bayesian network, thanks to the tools offered by this formalism, and to directly evaluate the influence of his decision on the objectives.