Publikasjoner
-
-
Jaramillo Jimenez, Veronica; Bouhmala, Noureddine & Gausdal, Anne Haugen
(2020).
Developing a predictive maintenance model for vessel machinery.
Journal of Ocean Engineering and Science.
ISSN 2468-0133.
5(4),
s. 358–386.
doi:
10.1016/j.joes.2020.03.003.
Vis sammendrag
The aim of maintenance is to reduce the number of failures in equipment and to avoid breakdowns that may lead to disruptions during operations. The objective of this study is to initiate the development of a predictive maintenance solution in the shipping industry based on a computational artificial intelligence model using real-time monitoring data. The data analysed originates from the historical values from sensors measuring the vessel´s engines and compressors health and the software used to analyse these data was R. The results demonstrated key parameters held a stronger influence in the overall state of the components and proved in most cases strong correlations amongst sensor data from the same equipment. The results also showed a great potential to serve as inputs for developing a predictive model, yet further elements including failure modes identification, detection of potential failures and asset criticality are some of the issues required to define prior designing the algorithms and a solution based on artificial intelligence. A systematic approach using big data and machine learning as techniques to create predictive maintenance strategies is already creating disruption within the shipping industry, and maritime organizations need to consider how to implement these new technologies into their business operations and to improve the speed and accuracy in their maintenance decision making.
-
Berntzen, Lasse; Florea, Adrian; Molder, Cristian & Bouhmala, Noureddine
(2019).
A Strategy for Drone Traffic Planning
Dynamic Flight-paths for Drones in Smart Cities.
I Berntzen, Lasse (Red.),
SMART 2019, The Eighth International Conference on Smart Cities, Systems, Devices and Technologies.
International Academy, Research and Industry Association (IARIA).
ISSN 978-1-61208-730-6.
s. 12–18.
Fulltekst i vitenarkiv
Vis sammendrag
This paper presents a solution for creating dynamic flight plans for drones. The number of drones is expected to increase dramatically, and there will be a demand for drone traffic planning solutions. The approach used here is based on a multidimensional grid with fixed top-level paths and lower-level paths used for local traffic between the departure and arrival points and the top-level paths. Flight plans may change dynamically if disruptions happen. The proposed solution includes the establishment of temporary no-fly zones and priority traffic.
-
Bouhmala, Noureddine; Oseland, Mats G.L & Brådland, Øystein
(2018).
Enhanced WalkSAT with Variable Neighborhood Search for MAX-SAT Problems.
I Bi, Yaxin; Kapoor, Supriya & Bhatia, Rahul (Red.),
Proceedings of SAI Intelligent Systems Conference (IntelliSys) 2016.
Springer.
ISSN 978-3-319-56993-2.
s. 368–376.
doi:
10.1007/978-3-319-56994-9_26.
Vis sammendrag
The maximum satisfiability problem which is known to be NP-hard problem plays a major role in both theoretical and applied computer science. Applying exact algorithms to such complex problems are doomed to fail when dealing with large optimization problems. This paper introduces an enhanced variant of the popular Walksat algorithm using a variable neighborhood structure model. This variant is based on one type of neighborhood with varying sizes. A set of industrial benchmark problem instances is used to test the effectiveness of the new algorithm.
-
Bouhmala, Noureddine
(2018).
Combining simulated annealing with local search heuristic for MAX-SAT.
Journal of Heuristics.
ISSN 1381-1231.
s. 1–23.
doi:
10.1007/s10732-018-9386-9.
Vis sammendrag
The simplicity of the maximum satisfiability problem combined with its wide applicability in various areas of artificial intelligence and computing science made it one of the fundamental optimization problems. This NP-complete problem refers to the task of finding a variable assignment that satisfies the maximum number of clauses in a Boolean Formula. The present consensus is that the best heuristic that leads to the best solutions for the partitioning of generic (random) graphs is a variable depth search due to Kernighan and Lin algorithm hereafter referred to as KL. It suggests an intriguing idea which is based on replacing the search of one favorable move by a search for a favorable sequence of moves. In this paper, an adapted version of KL for the maximum satisfiability problem is introduced and embedded into the simulated annealing algorithm. Tests on benchmark instances and comparison with state-of-the-art solvers quantify the power of the method.
-
Bouhmala, Noureddine; Øvergård, Kjell Ivar & Hjelmervik, Karina
(2018).
A Multilevel Evolutionary Algorithm Applied to the Maximum Satisfiability Problems
.
I Farhadi, Hamed (Red.),
Machine Learning: Advanced Techniques and Emerging Applications.
IntechOpen.
ISSN 978-1-78923-752-8.
s. 203–217.
doi:
10.5772/intechopen.72843.
Vis sammendrag
The maximum satisfiability problem that is known to be nondeterministic polynomial (NP) complete plays a central role problem in many applications in the fields of very large-scale integration (VLSI) computer-aided design, computing theory, artificial intelligence, and defense. Given a set of m clauses and n Boolean variables, the maximum satisfiability problem refers to the task of finding an assignment of values to the variables that maximizes the number of satisfied clauses (or minimizes the number of unsatisfied clauses) In this chapter, a multilevel evolutionary algorithm is proposed for the maximum satisfiability problem. The multilevel process works by grouping the variables defining the problem to form clusters, uses the clusters to define a new problem, and is repeated until the problem size falls below some threshold. The coarsest problem is then given an initial assignment of values to variables and the assignment is successively refined on all the problems starting with the coarsest and ending with the original
-
Schøyen, Halvor; Bjorbæk, Clemet Thærie; Steger-Jensen, Kenn; Bouhmala, Noureddine; Burki, Umar & Jensen, Tor Erik
[Vis alle 7 forfattere av denne artikkelen]
(2018).
Measuring the contribution of logistics service delivery performance outcomes and deep-sea container liner connectivity on port efficiency.
Research in Transportation Business and Management (RTBM).
ISSN 2210-5395.
doi:
10.1016/j.rtbm.2018.03.002.
Vis sammendrag
One objective for countries in the European common market is to optimize the performance of their multimodal logistics chains. The attainment of this goal requires the continuous development of container ports' performance, better customer satisfaction and - at the same time - to deter the occurrence of waste and bottleneck. Many regions in Europe are shifting from a single-port to a multi-port gateway situation; their ports frequently have overlapping hinterlands and are therefore increasingly facing competition and rivalry between each other. This paper examines container ports located in six countries: Denmark, Finland, Iceland, Norway, Sweden and the UK. It focuses on sensitivities to the inclusion of country-specific measurements on logistics service delivery performance outcomes on port efficiency. Port efficiency is measured with Data Envelopment Analysis (DEA). The results suggest that: (1) efficiency measurements for Danish, Finnish, Swedish and British ports are heavily influenced by whether logistics service delivery outcomes are included or not; (2) Icelandic and Norwegian ports appear to be not sensitive to whether logistics service delivery outcomes are included or not; (3) on average, the container ports located in countries that are directly called by deep-sea transcontinental container liners are over-performers and under-performers with regard to technical efficiency and scale efficiency, respectively. We further apply a second-stage regression analysis to explain the impact of country-specific contextual factors on DEA-based efficiency scores.
-
Bouhmala, Noureddine & Øvergård, Kjell Ivar
(2017).
Combining Genetic Algorithm with Variable Neighborhood Search for MAX-SAT.
I Zelinka, Ivan; Vasant, Pandian; Duy, Vo Hoang & Dao, Tran Trong (Red.),
Innovative Computing, Optimization and Its Applications.
Springer.
ISSN 978-3-319-66983-0.
s. 73–92.
doi:
10.1007/978-3-319-66984-7_5.
-
Bouhmala, Noureddine; Helgesen, Halvard Sanness & Mathisen, Knut Morten
(2017).
A multilevel genetic algorithm for the maximum constraint satisfaction problem.
Advances in Intelligent Systems and Computing.
ISSN 2194-5357.
576,
s. 3–15.
doi:
10.1007/978-3-319-58088-3_1.
Vis sammendrag
The constraint satisfaction problem is a useful and well-studied framework for the modeling of many problems rising in Artificial Intelligence and other areas of Computer Science. As many real-world optimization problems become increasingly complex and hard to solve, better optimization algorithms are always needed. Genetic algorithms (GA) which belongs to the class of evolutionary algorithms is regarded as a highly successful algorithm when applied to a broad range of discrete as well continuous optimization problems. This paper introduces a hybrid approach combining a genetic algorithm with the multilevel paradigm for solving the maximum constraint satisfaction problem. The promising performances achieved by the proposed approach is demonstrated by comparisons made to solve conventional random benchmark problems.
-
Bouhmala, Nourddine; Oseland, Mats G.L & Brådland, Øystein
(2017).
WalkSAT based-learning automata for MAX-SAT.
Advances in Intelligent Systems and Computing.
ISSN 2194-5357.
576,
s. 98–110.
doi:
10.1007/978-3-319-58088-3_10.
Vis sammendrag
Researchers in artificial intelligence usually adopt the Satisfiability paradigm as their preferred methods when solving various real worlds decision making problems. Local search algorithms used to tackle different optimization problems that arise in various fields aim at finding a tactical interplay between diversification and intensification to overcome local optimality while the time consumption should remain acceptable. The WalkSAT algorithm for the Maximum Satisfiability Problem (MAX-SAT) is considered to be the main skeleton underlying almost all local search algorithms for MAX-SAT. This paper introduces an enhanced variant of WalkSAT using Finite Learning Automata. A benchmark composed of industrial and random instances is used to compare the effectiveness of the proposed algorithm against state-of-the-art algorithms.
-
Bouhmala, Nourddine & Øvergård, Kjell Ivar
(2017).
Combining Genetic Algorithm with Variable Neighborhood Search for MAX-SAT.
I Vasant, Pandian & Duy, Vo Hoang (Red.),
COMPSE 2016, First EAI International Conference on Computer Science and Engineering..
EAI (European Alliance for Innovation).
ISSN 9781631901362.
doi:
10.4108/eai.27-2-2017.152347.
Vis sammendrag
Metaheuristics which have gain popularity for solving different optimization problems that arise in various fields aim at finding good solutions at a low cost. In this paper, a hybrid approach combining genetic algorithm (GA) with variable neighbourhood search (VNS) is proposed for solving the maximum satisfiability problem (MAX-SAT). VNS works by moving from one neighbourhood to another in order to avoid getting trapped in local optima. Results comparing GA with and without VNS are presented. Finally, GA combined with VNS is compared to highly efficient solvers from the MAX-SAT 2014 competition.
-
Bouhmala, Nourddine
(2016).
How Good is the Euclidean Distance Metric for the Clustering Problem.
I Matsuo, Tokuro; Kanzaki, Akimitsu; Komoda, Norihisa & Hiramatsu, Ayako (Red.),
2016 5th IIAI International Congress on
Advanced Applied Informatics: IIAI-AAI 2016.
IEEE (Institute of Electrical and Electronics Engineers).
ISSN 978-1-4673-8985-3.
s. 312–315.
doi:
10.1109/IIAI-AAI.2016.26.
Vis sammendrag
Data Mining is concerned with the discovery of interesting patterns and knowledge in data repositories. Cluster Analysis which belongs to the core methods of data mining is the process of discovering homogeneous groups called clusters. Given a data-set and some measure of similarity between data objects, the goal in most clustering algorithms is maximizing both the homogeneity within each cluster and the heterogeneity between different clusters. In this work, test cases are used to demonstrate that the Euclidean Distance widely in literature is not a suitable metric for capturing the quality of the clustering.
-
Bouhmala, Nourddine; Grøsland, Mikkel Syse & Volden-Freberg, Vetle
(2016).
Enhanced Metaheuristics with the Multilevel Paradigm for MAX-CSPs.
I Gervasi, Osvaldo; Murgante, Beniamino; Misra, Beniamino; Rocha, Ana Maria A.C.; Torre, Carmelo M.; Taniar, David; Apduhan, Bernady O.; Stankova, Elena & Wang, Shangguang (Red.),
Computational Science
and Its Applications –
ICCSA 2016.
Springer.
ISSN 978-3-319-42088-2.
s. 543–553.
doi:
10.1007/978-3-319-42089-9_38.
Vis sammendrag
As many real-world optimization problems become increasingly complex and hard to solve, better optimization algorithms are always needed. Nature inspired algorithms such as genetic algorithms and simulated annealing which belongs to the class of evolutionary algorithms are regarded as highly successful algorithms when applied to a broad range of discrete as well continuous optimization problems. This paper introduces the multilevel paradigm combined with genetic algorithm and simulated annealing for solving the maximum constraint satisfaction problem. The promising performances achieved by the proposed approach is demonstrated by comparisons made to solve conventional random benchmark problems.
-
Bouhmala, Nourddine; Viken, Anders & Lønnum, Jonas Blåsås
(2016).
A Multilevel K-Means Algorithm for the Clustering Problem,
Proceedings of
2016 IEEE International Conference on
Cloud Computing and Big Data
Analysis (ICCCBDA 2016).
IEEE (Institute of Electrical and Electronics Engineers).
ISSN 978-1-5090-2594-7.
s. 115–121.
doi:
10.1109/ICCCBDA.2016.7529544.
Vis sammendrag
Data Mining is concerned with the discovery of interesting patterns and knowledge in data repositories. Cluster Analysis which belongs to the core methods of data mining is the process of discovering homogeneous groups called clusters. Given a data-set and some measure of similarity between data objects, the goal in most clustering algorithms is maximizing both the homogeneity within each cluster and the heterogeneity between different clusters. In this work, a multilevel K-Means algorithm for the clustering problem is introduced. The approach suggests looking at the clustering problem as a hierarchical optimization process going through different levels evolving from a coarse grain to fine grain strategy. The clustering problem is solved by first reducing the problem level by level to a coarser problem where an initial clustering is computed. The clustering of the coarser problem is mapped back level-by-level to obtain a better clustering of the original problem by refining the intermediate different clustering using the popular K-Means algorithm. A benchmark using a number of data sets collected from a variety of domains is used to compare the effectiveness of the hierarchical approach against its single-level counterpart.
-
Bouhmala, Nourddine
(2016).
A Simple and Efficient Variable Neighborhood Structure
For The Satisfiability Problem.
I META, 2016 (Red.),
Proceedings of META’2016
6th International Conference on Metaheuristics
and Nature Inspired computing.
International Conference on Metaheuristics.
s. 126–133.
Vis sammendrag
The Satisfiability Problem (SAT) is viewed as one of the fundamental optimization
problems. This NP-complete problem refers to the task of finding a variable assignment
that satisfies all the clauses in a Boolean Formula. Most local search algorithms used to solve
SAT problems rely on the 1-flip neighborhood structure. This paper introduces a simple and
efficient variable neighborhood strategy. The effectiveness of this neighborhood structure is
tested using GSAT-RW and an evolutionary algorithm on various benchmark instances.
-
Bouhmala, Nourddine
(2016).
Combining Genetic Algorithm with the Multilevel Paradigm for the Maximum Constraint Satisfaction Problem.
I Pardalos, Panos M.; Conca, Piero; Giuffrida, Giovanni & Nicosia, Giuseppe (Red.),
Machine Learning,
Optimization,
and Big Data: Second International Workshop, MOD 2016
Volterra, Italy, August 26–29, 2016
Revised Selected Papers.
Springer.
ISSN 978-3-319-51468-0.
s. 330–340.
doi:
10.1007/978-3-319-51469-7_28.
Vis sammendrag
Genetic algorithms (GA) which belongs to the class of evolutionary algorithms are regarded as highly successful algorithms when applied to a broad range of discrete as well continuous optimization problems. This paper introduces a hybrid approach combining genetic algorithm with the multilevel paradigm for solving the maximum constraint satisfaction problem (Max-CSP). The multilevel paradigm refers to the process of dividing large and complex problems into smaller ones, which are hopefully much easier to solve, and then work backward towards the solution of the original problem, using the solution reached from a child level as a starting solution for the parent level. The promising performances achieved by the proposed approach are demonstrated by comparisons made to solve conventional random benchmark problems.
-
Bouhmala, Nourddine
(2016).
Enhanced Meta-heuristics with Variable Neighborhood Search Strategy for Combinatorial Optimization Problems.
Advances and Applications in Discrete Mathematics.
ISSN 0974-1658.
17(2),
s. 125–149.
doi:
10.17654/DM017020125.
Vis sammendrag
Variable neighborhood search (VNS) is a simple meta-heuristic that systematically changes the size and type of neighborhood during the search process in order to escape from local optima. In this paper, enhanced versions of tabu search and memetic algorithm with variable neighborhood search for combinatorial optimization problems are introduced. The set of constructed neighborhoods satisfies the property that each small neighborhood is a subset of a larger one. Most of the work published earlier on VNS starts from the first neighborhood and moves on to higher neighborhoods without controlling and adapting the ordering of neighborhood structures. The order in which the neighborhood structures have been selected in this paper during the search process offers a better mechanism for performing diversification and intensification. A set of industrial and random problems is used to test the effectiveness of the two enhanced meta-heuristics using the maximum satisfying problem as a test case.
-
Bouhmala, Nourddine
(2016).
A multilevel genetic algorithm for the clustering problem.
International Journal of Information and Communication Technology.
ISSN 1466-6642.
9(1),
s. 101–116.
doi:
10.1504/IJICT.2016.077692.
Vis sammendrag
Data mining is concerned with the discovery of interesting patterns and knowledge in data repositories. Cluster analysis which belongs to the core methods of data mining is the process of discovering homogeneous groups called clusters. Given a dataset and some measure of similarity between data objects, the goal in most clustering algorithms is maximising both the homogeneity within each cluster and the heterogeneity between different clusters. The multilevel paradigm suggests a hierarchical optimisation process going through different levels evolving from a coarse grain to fine grain strategy. The clustering problem is solved by first reducing the problem level by level to a coarser problem where an initial clustering is computed. The clustering of the coarser problem is mapped back level-by-level to obtain a better clustering of the original problem by refining the intermediate different clustering obtained at various levels. In this paper, a multilevel genetic algorithm and a multilevel K-means algorithm are introduced for solving the clustering problem. A benchmark using a number of datasets collected from a variety of domains is used to compare the effectiveness of the hierarchical approach against its single-level counterpart.
-
Bouhmala, Nourddine
(2016).
A variable neighbourhood search structure based-genetic algorithm for combinatorial optimisation problems.
International Journal of Intelligent Systems Technologies and Applications.
ISSN 1740-8865.
15(2),
s. 127–146.
doi:
10.1504/IJISTA.2016.076494.
Vis sammendrag
In this paper, a variable-neighbourhood-genetic-based-algorithm is proposed for the MAX-SAT problem. Most of the work published earlier on variable neighbourhood search (VNS) starts from the first neighbourhood and moves on to higher neighbourhoods without controlling and adapting the ordering of neighbourhood structures. The order in which the neighbourhood structures have been proposed during the search process in this work enables the genetic algorithm with a better mechanism for performing diversification and intensification. A set of benchmark problem instances is used to compare the effectiveness of the proposed algorithm against the standard genetic algorithm. We also report promising results when the proposed algorithm is compared with state-of-the-art solvers.
-
-
-
Bouhmala, Nourddine; Viken, Anders & Lønnum, Jonas Blåsås
(2015).
Enhanced Genetic Algorithm with K-Means for the Clustering Problem.
International Journal of Modeling and Optimization.
ISSN 2010-3697.
5(2),
s. 150–154.
doi:
10.7763/IJMO.2015.V5.452.
Vis sammendrag
Abstract—In this paper, an algorithm for the clustering problem using a combination of the genetic algorithm with the popular K-Means greedy algorithm is proposed. The main idea of this algorithm is to use the genetic search approach to generate new clusters using the famous two-point crossover and then apply the K-Means technique to further improve the quality of the formed clusters in order to speed up the search process.
Experimental results demonstrate that the proposed genetic algorithm combined with K-Means converges faster while producing the same quality of the clustering compared to the standard genetic algorithm.
-
Bouhmala, Nourddine
(2015).
A multilevel learning automata for MAX-SAT.
International Journal of Machine Learning and Cybernetics.
ISSN 1868-8071.
6,
s. 911–921.
doi:
10.1007/s13042-015-0355-4.
Vis sammendrag
The need to solve optimization problems of unprecedented sizes is becoming a challenging task. Utilizing classical methods of Operations Research often fail due to the exponentially growing computational effort. It is commonly accepted that these methods might be heavily penalized by the NP-Hard nature of the problems and consequently will then be unable to solve large size instances of a problem. Lacking the theoretical basis and guided by intuition, meta-heuristics are the techniques commonly used even if they are unable to guarantee an optimal solution. Meta-heuristics search techniques tend to spend most of the time exploring a restricted area of the search space preventing the search to visit more promising areas thereby leading to solutions of poor quality. In this paper, a multilevel learning automata and a multilevel WalkSAT algorithm are proposed as a paradigm for finding a tactical interplay between diversification and intensifi- cation for large scale optimization problems. The multi- level paradigm involves recursive coarsening to create a hierarchy of increasingly smaller and coarser versions of the original problem. This phase is repeated until the size of the smallest problem falls below a specified reduction threshold. A solution for the problem at the coarsest level is generated, and then successively projected back onto each of the intermediate levels in reverse order. The solution at each child level is improved before moving to the parent level. Benchmark including large MAX-SAT test cases are used to compare the effectiveness of the multilevel ap- proach against its single counter part.
-
Bouhmala, Nourddine
(2015).
A Variable Depth Search Algorithm for Binary Constraint Satisfaction Problems.
Mathematical Problems in Engineering.
ISSN 1024-123X.
2015.
doi:
10.1155/2015/637809.
Vis sammendrag
The constraint satisfaction problem (CSP) is a popular used paradigm to model a wide spectrum of optimization problems in artificial intelligence. This paper presents a fast metaheuristic for solving binary constraint satisfaction problems. The method can be classified as a variable depth search metaheuristic combining a greedy local search using a self-adaptive weighting strategy on the constraint weights. Several metaheuristics have been developed in the past using various penalty weight mechanisms on the constraints. What distinguishes the proposed metaheuristic from those developed in the past is the update of k variables during each iteration when moving from one assignment of values to another. The benchmark is based on hard random constraint satisfaction problems enjoying several features that make them of a great theoretical and practical interest. The results show that the proposed metaheuristic is capable of solving hard unsolved problems that still remain a challenge for both complete and incomplete methods. In addition, the proposed metaheuristic is remarkably faster than all existing solvers when tested on previously solved instances. Finally, its distinctive feature contrary to other metaheuristics is the absence of parameter tuning making it highly suitable in practical scenarios.
-
Bouhmala, Nourddine; Hjelmervik, Karina Bakkeløkken & Øvergård, Kjell Ivar
(2015).
A Generalized Variable Neighborhood Search For Combinatorial Optimization Problems.
Electronic Notes in Discrete Mathematics.
ISSN 1571-0653.
47,
s. 45–52.
doi:
10.1016/j.endm.2014.11.007.
Vis sammendrag
The VNS is a simple meta-heuristic that systematically changes the size and type of neighborhood during the search process in order to escape from local optima. In this paper, a generalized variable neighborhood search is proposed for combinatorial optimization problems. The set of constructed neighborhoods satisfies the property that each small neighborhood is a subset of a larger one. Most of the work published earlier on VNS starts from the first neighborhood and moves on to higher neighbor- hoods without controlling and adapting the ordering of neighborhood structures. The order in which the neighborhood structures have been selected in this paper during the search process offers a better mechanism for performing diversification and intensification. A set of industrial benchmark problem instances is used to test the effectiveness of the new variant of VNS using the maximum satisfying problem as a test case.
-
Bouhmala, Nourddine
(2014).
Enhanced Walksat With Finite Learning Automata for MAX-SAT.
International Journal of Combinatorial Optimization Problems and Informatics.
ISSN 2007-1558.
5(3),
s. 20–36.
doi:
10.1007/978-3-319-56994-9_26.
Vis sammendrag
Researchers in artificial intelligence usually adopt the constraint satisfaction problem and
the Satisfiability paradigms as their preferred methods when solving various real worlds decision
making problems. Local search algorithms used to tackle different optimization problems
that arise in various fields aim at finding a tactical interplay between diversification and intensification
to overcome local optimality while the time consumption should remain acceptable.
The Walksat algorithm for the Maximum Satisfiability Problem (MAX-SAT) is considered
to be the main skeleton underlying almost all local search algorithms for MAX-SAT. This
paper introduces an enhanced variant of Walksat using Finite Learning Automata. A benchmark
composed of industrial and random instances is used to compare the effectiveness of the
proposed algorithm against state-of-the-art algorithms.
-
Bouhmala, Nourddine
(2014).
A Variable Neighborhood Walksat-Based Algorithm for MAX-SAT Problems.
Scientific World Journal.
ISSN 1537-744X.
2014.
doi:
10.1155/2014/798323.
Vis sammendrag
The simplicity of the maximum satisfiability problem (MAX-SAT) combined with its applicability in many areas of artificial intelligence and computing science made it one of the fundamental optimization problems. This NP-complete problem refers to the task of finding a variable assignment that satisfies the maximum number of clauses (or the sum of weights of satisfied clauses) in a Boolean formula. The Walksat algorithm is considered to be the main skeleton underlying almost all local search algorithms for MAX-SAT. Most local search algorithms including Walksat rely on the 1-flip neighborhood structure. This paper introduces a variable neighborhood walksat-based algorithm. The neighborhood structure can be combined easily using any local search algorithm. Its effectiveness is compared with existing algorithms using 1-flip neighborhood structure and solvers such as CCLS and Optimax from the eighth MAX-SAT evaluation.
-
Bouhmala, Nourddine; Hjelmervik, Karina Bakkeløkken & Øvergård, Kjell Ivar
(2013).
Hybrid of evolutionary algorithm and multilevel paradigm to solve the satisfiability problem.
I Aboutajdine, D.; Skalli, A.; Benchekroun, B. & Artiba, A. (Red.),
Proceedings of 2013 International Conference on Industrial Engineering and Systems Management (IESM).
IEEE conference proceedings.
ISSN 978-2-9600532-4-1.
s. 1–4.
doi:
10.5772/intechopen.72843.
Vis sammendrag
In this work, a memetic algorithm that makes use of the multilevel paradigm for solving SAT problems is presented. The multilevel paradigm refers to the process of dividing large and difficult problems into smaller ones, which are hopefully much easier to solve, and then work backward towards the solution of the original problem, using a solution from a previous level as a starting solution at the next level. Results on real industrial instances are presented.
-
Bouhmala, Nourddine
(2013).
Multilevel diversification and intensification in metaheuristics,
2013 8th International Conference on Intelligent Systems: Theories and Applications (SITA).
IEEE conference proceedings.
ISSN 978-1-4799-0299-6.
doi:
10.1109/SITA.2013.6560793.
Vis sammendrag
The performance of metaheuristics deteriorates very rapidly because the complexity of the problem usually increases with its size and the solution space of the problem increases exponentially with the problem size. Because of these two issues, optimization search techniques tend to spend most of the time exploring a restricted area of the search space preventing the search to visit more promising areas, and thus leading to solutions of poor quality. Designing efficient optimization search techniques requires a tactical interplay between diversification and intensification. The former refers to the ability to explore many different regions of the search space, whereas the latter refers to the ability to obtain high quality solutions within those regions. In this paper, three well known metaheuristics (Tabu Search, Memetic Algorithm and Walksat) are used with the multilevel context. The multilevel strategy involves looking at the search as a process evolving from a k-flip neighborhood to the standard I-flip neighborhood-based structure in order to achieve a tactical interplay between diversification and intensification. Benchmark results exhibit good prospects of multilevel metaheuristics.
-
Radianti, Jaziar; Granmo, Ole-Christoffer; Bouhmala, Nourddine; Sarshar, Parvaneh; Yazidi, Anis & Gonzalez, Jose J
(2013).
Crowd Models for Emergency Evacuation: A Review Targeting Human-Centered Sensing.
I Sprague, Ralph H. (Red.),
46th Hawaii International Conference on System Sciences (HICSS).
IEEE (Institute of Electrical and Electronics Engineers).
ISSN 978-1-4577-1925-7.
s. 156–165.
doi:
10.1109/hicss.2013.155.
Vis sammendrag
Emergency evacuation of crowds is a fascinating
phenomenon that has attracted researchers from various
fields. Better understanding of this class of crowd
behavior opens up for improving evacuation policies and
smarter design of buildings, increasing safety. Recently, a
new class of disruptive technology has appeared: Humancentered
sensing which allows crowd behavior to be
monitored in real-time, and provides the basis for realtime
crowd control. The question then becomes: to what
degree can previous crowd models incorporate this
development, and what areas need further research? In
this paper, we provide a survey that describes some
widely used crowd models and discuss their advantages
and shortages from the angle of human-centered sensing.
Our review reveals important research opportunities that
may contribute to an improved and more robust
emergency management.
-
Bouhmala, Nourddine; Hjelmervik, Karina Bakkeløkken & Øvergård, Kjell Ivar
(2013).
Combining Evolutionary Algorithm With The Multilevel Paradigm For The Simulation Of Complex System,
Proceedings 27th European Conference on Modelling and Simulation ECMS 2013, May 27th - May 30th, 2013, Ålesund, Norway.
ECMS European Council for Modelling and Simulation.
ISSN 978-0-9564944-6-7.
s. 753–757.
doi:
10.7148/2013-0753.
Vis sammendrag
Evolutionary Algorithms have become an efficient tool to simulate large and complex systems that re- quire a huge amount of computational resources. Nev- ertheless, evolutionary algorithms may still suffer from either slow or premature convergence preventing the search to visit more promising areas, and thus leading to solutions of poor quality. In this work, the mul- tilevel paradigm is used in order to enhance the evo- lutionary algorithm’s performance for simulating large industrial instances. The multilevel paradigm refers to the process of dividing large and difficult problems into smaller ones, which are hopefully much easier to solve, and then work backward towards the solution of the original problem, using a solution from a previous level as a starting solution at the next level. Experimental results comparing the multilevel evolutionary algorithm against its single-level variant are presented.
-
Jensen, Bjørn; Bouhmala, Nourddine & Nordli, Thomas
(2013).
A novel tangent based framework for optimizing continuous functions.
Journal of Emerging Trends in Computing and Information Sciences (CIS).
ISSN 2079-8407.
4(2),
s. 239–247.
Vis sammendrag
We present a novel framework for optimizing continuous functions based on genetic algorithms (GAs). The framework
utilizes a scheme for approximating the slope of the functions in contrast to standard GA implementations which simply exploit the function values. We present experimental results which show that this adaption in general provides significantly higher accuracy compared to the standard GA implementations.
-
-
Bouhmala, Nourddine & Reiersen, Jon
(2013).
Segregation and the Evolution of Cooperation.
I Sun, Fuchun; Li, Tianrui & Li, Hongbo (Red.),
Knowledge Engineering and Management : Proceedings of the Seventh International Conference on Intelligent Systems and Knowledge Engineering.
Springer.
ISSN 978-3642378317.
s. 127–138.
-
Bouhmala, Nourddine & Salih, Sirar
(2012).
A multilevel tabu search for the maximum satisfiability problem.
International Journal of Communications, Network and System Sciences.
ISSN 1913-3715.
5(10),
s. 661–670.
doi:
10.4236/ijcns.2012.510068.
Vis sammendrag
The maximum satisfiability problem (MAX-SAT) refers to the task of finding a variable assignment that satisfies the maximum number of clauses (or the sum of weight of satisfied clauses) in a Boolean Formula. Most local search algo-rithms including tabu search rely on the 1-flip neighbourhood structure. In this work, we introduce a tabu search algo-rithm that makes use of the multilevel paradigm for solving MAX-SAT problems. The multilevel paradigm refers to the process of dividing large and difficult problems into smaller ones, which are hopefully much easier to solve, and then work backward towards the solution of the original problem, using a solution from a previous level as a starting solution at the next level. This process aims at looking at the search as a multilevel process operating in a coarse-to-fine strategy evolving from k-flip neighbourhood to 1-flip neighbourhood-based structure. Experimental results comparing the mul-tilevel tabu search against its single level variant are presented.
-
-
Bouhmala, Nourddine
(2012).
A multilevel memetic algorithm for large SAT-encoded problems.
Evolutionary Computation.
ISSN 1063-6560.
20(4),
s. 641–664.
doi:
10.1162/EVCO_a_00078.
Vis sammendrag
Many researchers have focused on the satisfiability problem and on many of its variants due to its applicability in many areas of artificial intelligence. This NP-complete problem refers to the task of finding a satisfying assignment that makes a Boolean expression evaluate to True. In this work, we introduce a memetic algorithm that makes use of the multilevel paradigm. The multilevel paradigm refers to the process of dividing large and difficult problems into smaller ones, which are hopefully much easier to solve, and then work backward toward the solution of the original problem, using a solution from a previous level as a starting solution at the next level. Results comparing the memetic with and without the multilevel paradigm are presented using problem instances drawn from real industrial hardware designs.
-
Bouhmala, Nourddine; Hjelmervik, Karina Bakkeløkken & Øvergård, Kjell Ivar
(2012).
Single vs hierarchical population-basedmemetic algorithm for SAT-encodedindustrial problems:a statistical comparison.
International Journal of Artificial Intelligence & Applications.
ISSN 0976-2191.
3(6),
s. 57–73.
doi:
10.5121/ijaia.2012.3607.
Vis sammendrag
In this work, a hierarchical population-based memetic algorithm for solving the satisfiability problem is
presented. The approach suggests looking at the evolution as a hierarchical process evolving from a coarse
population where the basic unit of a gene is composed of cluster of variables that represent the problem to
a fine population where each gene represents a single variable. The optimization process is carried out by
letting the converged population at a child level serve as the initial population to the parent level. A
benchmark composed of industrial instances is used to compare the effectiveness of the hierarchical
approach against its single-level counterpart.
-
Bouhmala, Nourddine & Granmo, Ole-Christoffer
(2011).
GSAT Enhanced with Learning Automata and Multilevel Paradigm.
International Journal of Computer Science Issues.
ISSN 1694-0784.
8(6),
s. 38–54.
Vis sammendrag
A large number of problems that occur in knowledge-representation, learning, very large scale integration technology (VLSI-design), and other areas of artificial intelligence, are essentially satisfiability problems. The satisfiability problem refers to the task of finding a satisfying assignment that makes a Boolean expression evaluate to True. The growing need for more efficient and scalable algorithms has led to the development of a large number of SAT solvers. This paper introduces two new techniques that combine finite learning automata and multilevel paradigm with the Greedy Satisfiability Algorithm (GSAT). We present a detailed comparative analysis of the new approaches using a benchmark set containing randomized and practical engineering applications from various domains.
-
Granmo, Ole-Christoffer & Bouhmala, Nourddine
(2010).
Using Learning Automata to Enhance Local-Search Based SAT Solvers with Learning Capability.
I Zhang, Yagang (Red.),
Application of Machine Learning.
IntechOpen.
ISSN 978-953-307-035-3.
s. 63–85.
Vis sammendrag
In this chapter we study a new application domain for LA, namely, the Satisfiability (SAT) problem. In brief, we demonstrate how the learning capability of LA can be incorporated into selected classical local-search based solvers for SAT-like problems, with the purpose of allowing improved performance by means of learning. Furthermore, we provide a detailed empirical evaluation of the resulting LA based algorithms, and we analyze the effect that the introduced learning has on the local-search based solvers.
-
Granmo, Ole-Christoffer & Bouhmala, Nourddine
(2010).
Enhancing Local-search based SAT Solvers with Learning Capability.
I Sharp, Bernadette & Fred, Ana (Red.),
ICAART 2010, 2nd International Conference on Agents and Artificial Intelligence, Proceedings.
Institute for Systems and Technologies of Information, Control and Communication.
ISSN 978-989-674-021-4.
s. 515–521.
Vis sammendrag
The Satisfiability (SAT) problem is a widely studied combinatorial optimization problem with numerous applications, including time tabling, frequency assignment, and register allocation. Among the simplest and most effective algorithms for solving SAT problems are stochastic local-search based algorithms that mix greedy hill-climbing (exploitation) with random non-greedy steps (exploration). This paper demonstrates how the greedy and random components of the well-known GSAT Random Walk (GSATRW) algorithm can be enhanced with Learning Automata (LA) based stochastic learning. The LA enhancements are designed so that the actions that the LA chose initially mimic the behavior of GSATRW. However, as the LA explicitly interact with the SAT problem at hand, they learn the effect of the actions that are chosen, which allows the LA to gradually and dynamically shift from random exploration to goal-directed exploitation. Randomized and structured problems from various domains, including SAT-encoded Logistics Problems, and Block World Planning Problems, demonstrate that our LA enhancements significantly improve the performance of GSATRW, thus laying the foundation for novel LA-based SAT solvers.
-
Bouhmala, Noureddine & Granmo, Ole-Christoffer
(2010).
Stochastic Learning for SAT- Encoded Graph Coloring Problems.
International Journal of Applied Metaheuristic Computing.
ISSN 1947-8283.
1(3),
s. 1–19.
doi:
10.4018/jamc.2010070101.
Vis sammendrag
The graph coloring problem (GCP) is a widely studied combinatorial optimization problem due to its numerous applications in many areas, including time tabling, frequency assignment, and register allocation. The need for more efficient algorithms has led to the development of several GC solvers. In this paper, the authors introduce a team of Finite Learning Automata, combined with the random walk algorithm, using Boolean satisfiability encoding for the GCP. The authors present an experimental analysis of the new algorithm?s performance compared to the random walk technique, using a benchmark set containing SAT-encoding graph coloring test sets.
-
Bouhmala, Noureddine & Granmo, Ole-Christoffer
(2010).
Combining finite learning automata with GSAT for the satisfiability problem.
Engineering Applications of Artificial Intelligence.
ISSN 0952-1976.
23(5),
s. 715–726.
doi:
10.1016/j.engappai.2010.01.009.
Vis sammendrag
A large number of problems that occur in knowledge-representation, learning, very large scale integration technology (VLSI-design), and other areas of artificial intelligence, are essentially satisfiability problems. The satisfiability problem refers to the task of finding a satisfying assignment that makes a Boolean expression evaluate to True. The growing need for more efficient and scalable algorithms has led to the development of a large number of SAT solvers. This paper reports the first approach that combines finite learning automata with the greedy satisfiability algorithm (GSAT). In brief, we introduce a new algorithm that integrates finite learning automata and traditional GSAT used with random walk. Furthermore, we present a detailed comparative analysis of the new algorithm's performance, using a benchmark set containing randomized and structured problems from various domains.
-
Bouhmala, Noureddine & Cai, Xing
(2008).
A Mulitlevel Greedy Algorithm for the Satisfiability Problem,
Greedy Algorithms.
IN-TECH.
s. 39–54.
-
Bouhmala, Noureddine; Bouhmala, Noureddine & Granmo, Ole-Christoffer
(2008).
Solving Graph Coloring Problems using Learning Automata,
Evolutionary Computation in Combinatorial Optimization : 8th European conference, EVOCOP 2008, Naples, Italy, March 26-28, 2008 : proceedings.
Springer.
ISSN 0302-9743.
s. 277–288.
Vis sammendrag
The graph coloring problem (GCP) is a widely studied combinatorial optimization problem due to its numerous applications including time tabling, frequency assignment, and register allocation. The growing need for more efficient algorithms has led to the development of several GCP solvers. In this paper, we introduce the first GSP solver that is based on learning automata (LA). In short, we enhance traditional random walk with LA-based learning capability encoding the GCP as Boolean satisfiability problem (SAT). Extensive experiments demonstrate that the LA significantly improve the performance of RW, thus laying the foundation of novel LA-based solution for the GCP.
-
Cai, Xing & Bouhmala, Noureddine
(2007).
A unified framework of multi-objective cost functions for partitioning unstructured finite element meshes.
Applied Mathematical Modelling.
ISSN 0307-904X.
31(9),
s. 1711–1728.
Vis sammendrag
Good performance of parallel finite element computations on unstructured meshes requires high-quality mesh partitioning. Such a decomposition task is normally done by a graph-based partitioning approach. However, the main shortcoming of graph partitioning algorithms is that minimizing the so-called edge cut is not entirely the same as minimizing the communication overhead. This paper thus proposes a unified framework of multi-objective cost functions, which take into account several factors that are not captured by the graph-based partitioning approach. Freely adjustable weighting parameters in the framework also promote a flexible treatment of different optimization objectives. A greedy-style post-improvement procedure is designed to use these cost functions to improve the quality of subdomain meshes arising from the graph-based partitioning approach. Both serial and parallel implementation of the post-improvement procedure have been done. Numerical experiments show that communication overhead can indeed be reduced by this improvement procedure, thereby increasing the performance of parallel finite element computations. (C) 2006 Elsevier Inc. All rights reserved.
-
Granmo, Ole-Christoffer; Bouhmala, Noureddine & Bouhmala, Noureddine
(2007).
Solving the Satisfiability Problem Using Finite Learning Automata.
International Journal of Computer Science and Applications.
ISSN 0972-9038.
4(3),
s. 15–29.
Vis sammendrag
A large number of problems that occur in knowledge-representation, learning, VLSI-design, and other areas of artificial intelligence, are essentially satisfiability problems. The satisfiability problem refers to the task of finding a truth assignment that makes a Boolean expression true. The growing need for more efficient and scalable algorithms has led to the development of several SAT solvers. This paper reports the first approach based on combining finite learning automata with metaheuristics. In brief, we introduce a new algorithm that combines finite learning automata with traditional random walk. Furthermore, we present a detailed comparative analysis of the new algorithm's performance, using a benchmark set containing instances from randomized distributions, as well as SAT-encoded problems from various domains
-
Bouhmala, Noureddine
(2005).
A combined local search method and simulated annealing to constraint satisfaction problems,
Proceedings of the Sixtewenth Australasian Workshop on Combinatorial Algoriths (AWOCA 2005).
University of Ballarat.
s. 429–438.
Vis sammendrag
Iterative local serach methods (ILS) are simple and yet pwerful metaheuristics that have shown very good results for different optimization problems. In this paper, we introduce a new iterative local search method for the constraint satisfaction problem. This novel ILS builds a sequence of locally optimal states through the iterative use of local search method followed by a perturbation or kick bases on a mechanism borrowed from th esimulated annealing algorithm to guide the search. The reported results on binary random generated instances demonstrate the superiority of the approach when compared to GCSP
-
Meseguer, Pedro; Bouhmala, Noureddine; Bouzoubaa, Taoufik & Sanchez, Marti
(2004).
Current approaches for solving over-constrained problems.
Constraints.
ISSN 1383-7133.
8,
s. 9–39.
Vis sammendrag
We summarize existing approaches to model and solve overconstrained problems. These problems are usually formulated as combinatorial optimization problems, and different specific and generic formalisms are discussed, including the special case of multi-objective optimization. Regarding solving methods, both systematic and local search approaches are considered. Finally we review a number of case studies on overconstrained problems taken from the specialized literature.
-
Bouhmala, Noureddine; Natvig, T. & Jakobsen, M.
(2003).
A multilevel construction algorithm for the travelling salesman problem,
Optimation and optimal control.
World Scientific.
s. 29–35.
-
Meseguer, Pedro; Bouhmala, Noureddine; Bouzoubaa, Taoufik; Irgens, Morten & Sanchez, Marti
(2003).
Current Approaches for Solving Over-Constrained Problems.
Constraints.
ISSN 1383-7133.
doi:
10.1023/A:1021902812784.
Vis sammendrag
We summarize existing approaches to model and solve overconstrained problems. These problems are usually formulated as combinatorial optimization problems, and different specific and generic formalisms are discussed, including the special case of multi-objective optimization. Regarding solving methods, both systematic and local search approaches are considered. Finally we review a number of case studies on overconstrained problems taken from the specialized literature.
-
Bouhmala, Noureddine & Pahud, Michel
(1998).
A parallel variant of simulated annealing for optimizing mesh partitions on workstations.
Advances in Engineering Software.
ISSN 0965-9978.
29,
s. 481–485.
Se alle arbeider i Cristin
-
Suma, V.; Bouhmala, Noureddine & Wang, Haoxiang
(2021).
Evolutionary Computing and Mobile Sustainable Networks - Proceedings of ICECMSN 2020.
Springer.
ISBN 978-981-15-5257-1.
2021(1).
1008 s.
Se alle arbeider i Cristin
-
Nordli, Thomas & Bouhmala, Noureddine
(2021).
Look-Ahead Based Meta-Heuristics for Continuous Optimization.
Vis sammendrag
By combining meta-heuristics with local search methods, a balancing of diversification and intensification can be achieved and thus mitigate problems such as premature convergence often found in meta-heuristics, such as Genetic algorithms and Simulated annealing. The main idea: Using the variable depth search Kernighan-Lin algorithm as the local search method in such a hybrid approach. The work presented, applies two such hybrid approaches on continuous optimization problems. Their performance are evaluated using a set of well known optimization test functions.
-
-
Yazidi, Anis; Bouhmala, Noureddine & Goodwin, Morten
(2020).
A team of pursuit learning automata for solving deterministic optimization problems.
Applied intelligence (Boston).
ISSN 0924-669X.
50,
s. 2916–2931.
doi:
10.1007/s10489-020-01657-9.
Vis sammendrag
Learning Automata (LA) is a popular decision-making mechanism to “determine the optimal action out of a set of allowable actions” [1]. The distinguishing characteristic of automata-based learning is that the search for an optimal parameter (or decision) is conducted in the space of probability distributions defined over the parameter space, rather than in the parameter space itself [2]. In this paper, we propose a novel LA paradigm that can solve a large class of deterministic optimization problems. Although many LA algorithms have been devised in the literature, those LA schemes are not able to solve deterministic optimization problems as they suppose that the environment is stochastic. In this paper, our proposed scheme can be seen as the counterpart of the family of pursuit LA developed for stochastic environments [3]. While classical pursuit LAs can pursue the action with the highest reward estimate, our pursuit LA rather pursues the collection of actions that yield the highest performance by invoking a team of LA. The theoretical analysis of the pursuit scheme does not follow classical LA proofs, and can pave the way towards more schemes where LA can be applied to solve deterministic optimization problems. Furthermore, we analyze the scheme under both a constant learning parameter and a time-decaying learning parameter. We provide some experimental results that show how our Pursuit-LA scheme can be used to solve the Maximum Satisfiability (Max-SAT) problem. To avoid premature convergence and better explore the search space, we enhance our scheme with the concept of artificial barriers recently introduced in [4]. Interestingly, although our scheme is simple by design, we observe that it performs well compared to sophisticated state-of-the-art approaches.
-
-
Bouhmala, Nourddine
(2013).
A Multilevel K-Means Algorithm for The Clustering Problem.
-
Bouhmala, Nourddine; Hjelmervik, Karina Bakkeløkken & Øvergård, Kjell Ivar
(2013).
Combining Evolutionary Algorithm With The Multilevel Paradigm For The Simulation Of Complex System.
Vis sammendrag
Evolutionary Algorithms have become an efficient tool to simulate large and complex systems that re- quire a huge amount of computational resources. Nev- ertheless, evolutionary algorithms may still suffer from either slow or premature convergence preventing the search to visit more promising areas, and thus leading to solutions of poor quality. In this work, the mul- tilevel paradigm is used in order to enhance the evo- lutionary algorithm’s performance for simulating large industrial instances. The multilevel paradigm refers to the process of dividing large and difficult problems into smaller ones, which are hopefully much easier to solve, and then work backward towards the solution of the original problem, using a solution from a previous level as a starting solution at the next level. Experimental results comparing the multilevel evolutionary algorithm against its single-level variant are presented.
-
-
-
Bouhmala, Nourddine; Hjelmervik, Karina Bakkeløkken & Øvergård, Kjell Ivar
(2012).
Improving the asymptotic convergence of memetic algorithms: The SAT problem case study.
Vis sammendrag
In this work, a memetic algorithm that makes use of the multilevel paradigm for solving SAT problems is presented. The multilevel paradigm refers to the process of dividing large and difficult problems into smaller ones, which are hopefully much easier to solve, and then work backward towards the solution of the original problem, using a solution from a previous level as a starting solution at the next level. Results on real industrial instances are presented.
-
Bouhmala, Noureddine & Cai, Xing
(2009).
A Multilevel Approach for the Satisfiability Problem.
ISAST Transactions on Computers and Intelligent Systems.
ISSN 1798-2448.
2(1),
s. 29–37.
Vis sammendrag
A large number of problems that occur in knowledge-representation, learning, VLSI design,and other areas of artificial intelligence are essentially satisfiability problems. The satisfiability problem refers to the task of finding a true assignment that makes a boolean expression true. The growing need for more efficient and scalable algorithms have led to the development of several SAT solvers. In this paper, we introduce a multilevel approach combining the multilevel paradigm with the GSAT greedy algorithm for solving the satisfiability problem. We present a comparative analysis of the new algorithm's performance using a benchmark set containing randomized and structured problems from various domains. SAT, GSAT, multilevel optimization, combinatorial optimization
-
Bouhmala, Noureddine
(2005).
A new interactive local-search method for constraint satisfaction problems.
Vis sammendrag
Iterative local search methods (ILS) are simple and yet powerful metaheuristics that have shown very good results for different optimization problems. In this paper, we introduce a new iterative local search method for the constraint satisfaction problem. This novel ILS builds a sequence of locally optimal states through the iterative use of local search method followed by a perturbation or kick to guide the search to promising areas of the search space. The reported results on binary random generated instances demonstrate the superiority of the approach when compared to the simulated annealing method.
-
Bouhmala, Noureddine
(2004).
Combining local search and genetic algorithms with the multilevel pradigm for the travelling salesman problem.
Vis sammendrag
Multilevel refinement schemes refer to the process of dividing large and difficult problems into smaller ones, which are hopefully much easier to solve, and then work backward towards the solution of the original problem, using a solution from a previous level as a starting solution for the next level. In this paper, we present a multilevel genetic algorithm and a multilevel construction algorithms start by coarseining the original problem into a sequence of smaller problems using a coarsening scheme. Thereafter a tour is determined at the smallest problem and is projected back to the original problem by going through a refinement phase at each intermediate level. We present experimental results to demonstrate the effectiveness of these two multilevel algorithms.
-
Bouhmala, Noureddine
(2003).
Multilevel techniques for the travelling salesman problem.
-
Bouhmala, Noureddine
(2003).
A multilevel genetic algorithm for the travelling salesman problem.
-
Bouhmala, Noureddine; Natvig, T. & Jakobsen, M.
(2003).
A multilevel construcion algorithm for the traveling salesman problem.
-
Bouhmala, Noureddine
(1999).
An Experimental Comparison of Different Graph Coarsening Schemes.
Ecole Polytechnique Federale de Lausanne.
-
Bouhmala, Noureddine
(1999).
Greedy Algorithms for Partitioning Graphs.
Ecole Polytechnique Federale de Lausanne.
Se alle arbeider i Cristin
Publisert
16. apr. 2024 11:05