Y. Dimopoulos |
S. Likothanasis |
K. Stergiou |
TABLE OF CONTENTS
1. INTRODUCTION
2. CONSTRAINT SATISFACTION PROBLEMS
3. PROPOSITIONAL SATISFIABILITY
1. INTRODUCTION
This chapter tries to cover the recent advances in search and constraint satisfaction made by the Greek AI research community. It is divided into three sub-chapters. The first one is concerned with constraint satisfaction problems and constraint programming. The second one covers the topic of propositional satisfiability. Finally, the third sub-chapter is devoted to evolutionary algorithms. All three are successful approaches for solving hard combinatorial decision and optimization problems and have received considerable attention by the AI community worldwide. Each sub-chapter starts with a brief introduction on the topic covered and proceeds by summarizing the contributions of the various research groups working on search and constraint satisfaction.
2. CONSTRAINT SATISFACTION PROBLEMS
Constraint Programming (CP) is a programming paradigm widely used for modeling and solving combinatorial decision and optimization problems from areas such as planning and scheduling, resource allocation, timetabling, configuration, hardware and software verification, etc. A problem is solved with CP by first modeling it as a constraint satisfaction or optimization problem and then applying techniques usually implemented within a constraint programming language/toolkit. The Constraint Satisfaction Problem (CSP), which is at the heart of CP, consists of:
- a finite set of variables X={x1,…,xn},
- a set of domains D={D(x1),…,D(xn)}; one for each variable, and
- a set of constraints C={c1,…,cm}.
Each constraint c, defined on some subset {x1,…,xk} of X, called the scope of c, restricts the allowed combinations of values for the variables in the scope of the constraint. A feasible solution to a CSP is an assignment of values to all variables such that all constraints are satisfied. A constraint optimization problem is a CSP together with an optimization function involving some of the variables in the problem. In this case, the aim is to find an optimal solution. That is, a feasible solution that maximizes (or minimizes) the optimization function.
Despite the simple problem formulation, CSP’s are expressive enough to model of a diversity of problems and particularly industrial applications such as timetabling and crew rotation. Consequently, the area has attracted significant research interest in the past two decades that led to a number of solving techniques attacking various aspects of the CSP problem. Probably the most well studied techniques involve local filtering algorithms applied to a CSP problem, i.e. transformations of the original problem to one that retains the set of solutions but presents a smaller search space. These transformations involve removing values from variable domains that cannot possibly participate in the final solution by exploiting information that resides in the constraints. Research was mainly focused on filtering algorithms for binary constraints, with a significant number of successful results, under the assumption that higher order constraints can be encoded as binary in a straightforward manner. However, further investigation proved that the case of binary encodings requires the application of specialized filtering algorithms in order to yield any benefits, and additionally, local filtering algorithms for non-binary constraints have been proposed. Since the application of filtering algorithms introduces an additional computational cost, distributed versions have been proposed to reduce the execution time, with some success. Filtering algorithms play also a central part in the variations of the standard CSP, such as the Quantified CSP where the existence of universally quantified variables over a domain is permitted and the Stohastic CSP, in which some variables receive values probabilistically according to a distribution.
The application of filtering does not (necessarily) lead to a solution and search is still required that in some cases can benefit significantly by the introduction of heuristics regarding variable and value ordering during search or combining local search techniques with constructive ones. Finally, most real-world applications involve searching for optimal solutions of a CSP. Although the original approach of the field involved that application of "simple" branch-and-bound algorithms, more efficient methodologies involve combining research results from other fields such as Operations Research, employing AI techniques such as machine learning, or even the introduction of specialized optimization algorithms.
In the past few years research on CSPs has been carried out at the following academic departments in Greece: Department of Information and Communication Systems Engineering at the University of the Aegean, Department of Informatics and Telecommunications at the University of Athens, Department of Informatics at the Aristotle University of Thessaloniki, Department of Management Science and Technology at the Athens University of Economics and Business, Department of Economics at the University of Patras. Despite the relatively small number of people working in the field, the Greek constraint community has delivered a number of interesting research and application results in a number of topics mentioned above that are described in the sections that follow.
University of the Aegean
Research on CSPs at the University of the Aegean has been carried out within the AI Lab at the Department of Information and Communication Systems Engineering. This research has focused on binary encodings of non-binary constraints, quantified and stochastic CSPs, local consistency algorithms, modeling, and most recently, on autonomous and adaptive search.
It is well-known that any non-binary constraint can be translated into a set of binary ones using either the dual or the hidden variable encoding. However, this process results in exponential memory consumption and loss of potentially crucial semantic information. On the other hand, solving methods for binary constraints have been studied and developed to a greater extent than for non-binary ones. Research in the AI Lab, in collaboration with N. Samaras from the University of Macedonia, demonstrated that transforming non-binary constraints into binary can very rarely pay off, unless methods specifically developed for the binary encodings are applied. Hence, new specialized arc consistency algorithms were developed for both the hidden variable and the dual encoding [1]. Experimental results on a wide range of problems demonstrated that when such methods are used, translating non-binary constraints into binary can sometimes be very beneficial.
Quantified CSPs (QCSPs) extend the standard CSP framework by allowing for the presence of universally quantified variables as well as standard existentially quantified ones. Universal variables can be used to model events or actions that are beyond the control of the problem solving agent while existential variables are controlled and can be set by the agent. In this way, many problems from areas such as planning and scheduling under uncertainty, adversarial games, interactive configuration, model checking, hardware/software verification, etc., that are beyond the modeling capabilities of CSPs, can be modeled and solved as QCSPs. The main decision task in a QCSP is to determine whether for any sequence of assignments to the universal variables in the problem there exists a sequence of assignments to the existential variables such that no constraint is violated. It is known that this task is PSPACE-Complete. Research in the AI Lab, in collaboration with I. Gent and P. Nightingale from the University of St. Andrews, resulted in the development of QCSP-Solve, the first non-trivial solver for binary QCSPs [2,3]. QCSP-Solve integrates various techniques either adapted from the related area of QBF and from CSPs, or developed specifically for the QCSP. These include an algorithm for applying arc consistency, developed jointly with N. Mamoulis from the University of Hong Kong [4], the pure value rule, conflict-directed backjumping and solution directed pruning [2]. More recently, in collaboration with F. Bacchus, QCSP-Solve was enhanced by augmenting it with solution-directed backjumping [5]. In addition to QCSP-Solve, an alternative solver based on repair-based techniques has been developed [6].
The Stochastic CSP is a proactive framework for modeling constraint problems under uncertainty introduced by T. Walsh. In this framework the variables are divided into decision ones which the problem solving agent can set and stochastic ones that receive random values according to a probability distribution. The aim is to find a policy for setting the decision variables so that the probability of satisfying the constraints in the problem is maximized whatever the values of the stochastic variables. The AI Lab contributed to the study of the stochastic CSP by first identifying and correcting an error in the forward checking algorithm proposed by Walsh, and then by showing how the concept of arc consistency can be defined in stochastic CSPs and how it can be used to devise a filtering algorithm [7].
Local consistency methods, such as arc consistency, are crucial for the success of CP. Domain filtering consistencies that only delete values from domains are particularly useful because they have a low space complexity and do not require complex restoration work upon backtracking. Although many such consistencies have been proposed for binary constraints, only very few existed for non-binary ones until very recently. Work in the AI Lab in collaboration with C. Bessiere and T. Walsh resulted in the definition and theoretical evaluation of numerous domain filtering consistencies for non-binary problems [8,9,10]. These include restricted pairwise consistency (RPWC), max restricted pairwise consistency (maxRPWC), and inverse ω-consistency (IωC). Also, several algorithms for these consistencies were proposed and implemented. Experimental results demonstrated that some of the new consistencies are very promising for certain classes of non-binary problems.
Local consistency methods are also important in SAT which is a subclass of the CSP where all variables have Boolean domains and all constraints are specified as clauses in CNF. As CSPs and SAT are both highly researched areas, an important question concerning their relation is whether and under what circumstances it is beneficial to translate a problem stated in one of the formalisms into the other formalism. Numerous methods to perform such a translation have been proposed for both directions. Research in the AI Lab performed jointly with Y. Dimopoulos from the University of Cyprus resulted in a theoretical study comparing the pruning power that various local consistency methods can achieve in the CSP to that of corresponding methods for SAT under various translations from one framework to the other [11].
Most recently, research efforts in the AI Lab have focused on autonomous and adaptive search methods and heuristics for CSPs. Building autonomous solvers and developing algorithms and heuristics that can adapt their behavior during search are major challenges in CP. The AI Lab has contributed by developing heuristics for automatically switching between different propagation techniques during search [12]. This is achieved through monitoring and reacting to certain propagation events like value deletions and domain wipe-outs. In addition, new adaptive conflict-directed variable ordering heuristics have been developed and evaluated [13]. Also, adaptive heuristics for ordering the elements of the propagation list, when for example maintaining arc consistency, have been developed [14].
Finally, in joint work with N. Mamoulis, the potential of using CP technology to model and solve queries in XML was explored [15]. It was demonstrated that a large subclass of queries expressible in XPath1 can be easily modeled as CSPs and solved in polynomial time using constraint propagation methods. Also, a specialized constraint that can be used to model common intractable queries was introduced together with an efficient filtering algorithm.
Athens University of Economics and Business and University of Patras
Joint research efforts by D. Magos at the Athens University of Economics and Business and I. Mourtos at the University of Patras have focused on the following:
- The integration of Integer Programming and Constraint Programming methods in order to obtain more efficient algorithms for identifying a feasible or an optimal solution. Algorithms of this type have extensively been tested on instances of the Mutually Orthogonal Latin Squares problem, while the implications of the computational results obtained may be valuable for other problems and especially for problems exhibiting a multi-index assignment structure [16,17].
- The linearization of systems of logic predicates and particularly of systems of all_different predicates through the analysis of the polytope defined as the convex hull of integer vectors satisfying simultaneously all predicates. That includes the identification of facet-defining inequalities, the derivation of polynomial-time separation algorithms and the incorporation of those inequalities as cutting planes within a Branch & Cut algorithm [18,19].
- Efficient algorithms accomplishing hyperarc consistency for structured combinatorial optimization problems like matching [20] and stable admissions [21]. Such algorithms remove all domain values that never appear in a feasible solution of some non-binary constraint.
- The complexity of finding the persistency partition of a ground set with respect to the complexity of finding a maximum weight independent set. The term persistency is an alternative to consistency, since it refers to identifying (i) variables of the problem set to the same values at every optimal solution and/or (ii) values in the domains of certain variables that never appear at an optimal solution [22].
University of Athens
The Constraint Programming and Scheduling Applications research group of the Department of Informatics and Telecommunications of the University of Athens is working in the areas of constraint satisfaction, constraint programming, and scheduling for almost twenty years. The group participated in a number of European Union projects, in the context of the ESPRIT Program, namely EDS, APPLAUSE, PARACHUTE and PARROT. One project funded by Olympic Airways was also carried out by the group, as well as a number of internal University projects.
Focusing on the most recent work carried out by the group, one of the main problems that was dealt with is the crew scheduling problem. Algorithms and methodologies to tackle the problem were developed. Most of them were based on constraint programming methodologies. Hybrid approaches that combine constraint programming and operations research techniques were developed [23]. In addition, a method based on constraint logic programming was designed and implemented [24], as well as one based on genetic algorithms [25].
Another problem that the group worked on, and is still working, is the timetabling problem. Initially, the work was based on constraint logic programming techniques, but eventually, effort was put on changing the modeling and implementation platform to an object-oriented one, namely C++ in conjunction with Ilog Solver [26]. The work of the group on various scheduling problems resulted in the development of two C++ libraries, namely Naxos Solver, which provides a number of classes for constraint programming, as well as Amorgos Solver, a library which provides a number of search methods that may be used, in conjuction with Naxos Solver, to tackle constraint satisfaction problems with large search spaces. These two libraries will be made available publicly very soon. The latest timetabling system that has been developed by the group on top of Naxos and Amorgos solvers is available, currently with a Web interface only in Greek, at http://www.di.uoa.gr/~orprog. This system may be used freely by high schools or university departments to construct their course timetables.
Other work conducted by the group in the specified areas is related to the introduction of a heuristic backbone sampling algorithm to deal with the maximum satisfiability problem [27], the proposal of an approach to exploit instance-based machine learning in order to guide the search in combinatorial optimization problems [28,29], a study of the intrinsic hardness and available choices in the search spaces of constraint satisfaction problems [30, 31] and the introduction of an algorithm that combines constructive and local search to tackle constraint satisfaction problems [32].
Aristotle University of Thessaloniki
Research at the Logic Programming and Intelligent Systems Group (LPIS-http://lpis.csd.auth.gr) of the Aristotle University of Thessaloniki has focused on distributed constraint satisfaction. Although imposing a higher order of consistency in a CSP problem greatly reduces the search space, the cost of applying consistency checking algorithms is significant, sometimes prohibitive to their application. One way to overcome this disadvantage is to reduce the overall execution time through distribution over a network of agents. This approach is further supported by the availability of a large number of machines connected through some network and provides an elegant solution to solving hard problems. Thus, distributed constraint satisfaction has long been the topic of active research and a large number of approaches that address the problem have been reported in the literature. Currently the algorithms proposed in the literature fall under two classes:
- distributed filtering algorithms, such as massively parallel versions of the AC-4 algorithm, coarse-grained versions of AC-4 and AC-9, and distributed algorithms based on the notion of domain reduction functions, etc, and
- distributed search algorithms, such as asynchronous and distributed backtracking search, were the problem is divided among a number of agents that cooperate towards a solution through a message passing scheme.
Singleton Consistency defines a class of filtering methods that demonstrates a high pruning efficiency but at a high computational cost. Research in LPIS resulted in the DSAC algorithm [33] which is a distributed version of the singleton consistency that aims to reduce the execution time but also to provide a simple distributed consistency algorithm that can be implemented in any existing constraint programming system without major modifications. The principle behind the algorithm is rather simple. Agents in the community have a ``complete'' view of the problem, but enforce singleton consistency to a subset of the domain variables. Changes in the domains that are detected by the consistency algorithm are broadcasted to all agents participating in the society. The experimental results show a significant speedup of the distributed version compared to the sequential one.
The DSAC algorithm is very similar to the DisAC-4, with the difference that a singleton arc consistency algorithm is employed for detecting and treating inconsistencies and thus the benefits expected from the application of the algorithm are greater. A major advantage of the DSAC algorithm is simplicity. The distributed version of the singleton consistency algorithm has very little modifications with respect to the sequential one, and thus can be easily implemented on top of any constraint system as it has been done in [34], where the implementation was done in the Distributed Constraint Platform CSPCONS [35].
Conclusion
Constraint satisfaction is one of the most promising, attractive and active research areas in the AI community. This stems partly from the fact that there are a large number of real-world industrial applications that drive and pose new challenges to the community and partly from the fact that being a multidisciplinary area it offers a great number of opportunities for combining research results. Although, research in Greece has not yet attracted the number of researchers expected, given the significance of the field, still the community is very active with contributions to the international research fora.
References
[1] N. Samaras and K. Stergiou (2005), Binary Encodings of Non-binary Constraint Satisfaction Problems: Algorithms and Experimental Results. Journal of Artificial Intelligence Research (JAIR). 24: 641-684
[2] I. Gent, P. Nightingale and K. Stergiou, QCSP-Solve: A Solver for Quantified Constraint Satisfaction Problems. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI-05) 138-143, 2005.
[3] I. Gent, P. Nightingale. A. Rowley and K. Stergiou (2008). Solving Quantified Constraint Satisfaction Problems. Artificial Intelligence 172 (6-7):738-771
[4] N. Mamoulis and K. Stergiou (2004). Algorithms for Quantified Constraint Satisfaction Problems. Proceedings of the 10th International Conference on Principles and Practice of Constraint Programming (CP-2004) 752-756
[5] F. Bacchus and K. Stergiou (2007). Solution Directed Backjumping for QCSP. Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming (CP 2007) 148-163
[6] K. Stergiou (2005). Repair-based Methods for Quantified CSPs. Proceedings of the 11th International Conference on Principles and Practice of Constraint Programming (CP-2005) 652-666
[7] T. Balafoutis and K. Stergiou (2006). Algorithms for Stochastic CSPs. Proceedings of the 12th International Conference on Principles and Practice of Constraint Programming (CP 2006) 44-58
[8] K. Stergiou and T. Walsh (2006). Inverse Consistencies for Non-Binary Constraints. Proceedings of the 17th European Conference on Artificial Intelligence (ECAI-2006) 153-157
[9] K. Stergiou (2007). Strong Inverse Consistencies for Non-binary CSPs. Proceedings of the 19th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2007) 215-222
[10] C. Bessiere, K. Stergiou and T. Walsh (2008). Domain Filtering Consistencies for Non-binary Constraints. Artificial Intelligence 172 (6-7):800-822
[11] Y. Dimopoulos and K. Stergiou (2006). Propagation in CSP and SAT. Proceedings of the 12th International Conference on Principles and Practice of Constraint Programming (CP 2006) 137-151
[12] K. Stergiou (2008). Heuristics for Dynamically Adapting Propagation. Proceedings of the 18th European Conference on Artificial Intelligence (ECAI-2008).
[13] T. Balafoutis and K. Stergiou (2008). On conflict-driven variable ordering heuristics. Proceedings of the ERCIM Workshop on Constraint Solving and Constraint Logic Programming (CSCLP 2008)
[14] T. Balafoutis and K. Stergiou (2008). Exploiting Constraint Weights for Revision Ordering in Arc Consistency Algorithms. Proceedings of the ECAI 2008 Workshop on Modeling and Solving Problems with Constraints
[15] N. Mamoulis and K. Stergiou (2004). Constraint Satisfaction in Semi-structured Data Graphs. In Proceedings of the 10th International Conference on Principles and Practice of Constraint Programming (CP-2004) 393-407
[16] G. Appa, D. Magos and I. Mourtos (2006). Searching for Mutually Orthogonal Latin Squares via Integer and Constraint Programming. European Journal of Operational Research 173, 519-530
[17] G. Appa, I. Mourtos and D. Magos (2002). Integrating Constraint and Integer Programming for the Orthogonal Latin Squares Problem. Proceedings of CP 2002, 17-32. Lecture Notes in Computer Science 2470
[18] G. Appa, D. Magos and I. Mourtos (2005). On the system of two all_different predicates. Information Processing Letters 94, 99-105
[19] G. Appa, D. Magos and I. Mourtos (2004). LP relaxations of multiple all_different predicates, Proceedings of CPAIOR 2004, 364-369. Lecture Notes in Computer Science 3011
[20] D. Magos, I. Mourtos and L. Pitsoulis (2006). Consistency of the matching predicate, Lecture Notes in Artificial Intelligence 3955, 555–558
[21] P. Eirinakis, D. Magos, I. Mourtos, Ioannis, P. Miliotis (2007). Hyperarc Consistency for the Stable Admissions Problem. Proceedings of the 19th IEEE International Conference on Tools with Artificial Intelligence, 2007. ICTAI 2007 Volume: 1, 239-242
[22] D. Magos, I. Mourtos and L. Pitsoulis: Persistency and matroid intersection. Computational Management Science, in press.
[23] M. Sellmann, K. Zervoudakis, P. Stamatopoulos, T. Fahle (2002). Crew Assignment via Constraint Programming: Integrating Column Generation and Heuristic Tree Search. Annals of Operations Research, Vol. 115, pp. 207-225
[24] G. Christodoulou and P. Stamatopoulos (2002). Crew Assignment by Constraint Logic Programming. Proceedings of the 2nd Hellenic Conference on Artificial Intelligence SETN-2002 (Companion Volume), pp. 117-127
[25] H. Kornilakis, P and Stamatopoulos (2002). Crew Pairing Optimization with Genetic Algorithms. Proceedings of the 2nd Hellenic Conference on Artificial Intelligence SETN-2002, LNAI 2308, pp. 109-120
[26] K. Zervoudakis and P. Stamatopoulos (2001). A Generic Object-Oriented Constraint Based Model for University Course Timetabling. Proceedings of the 3rd International Conference on the Practice and Theory of Automated Timetabling PATAT 2000, LNCS 2079, pp. 28-47
[27] O. Telelis and P. Stamatopoulos (2002). Heuristic Backbone Sampling for Maximum Satisfiability. Proceedings of the 2nd Hellenic Conference on Artificial Intelligence SETN-2002 (Companion Volume), pp. 129-139
[28] O. Telelis and P. Stamatopoulos (2002). Guiding Constructive Search with Statistical Instance-Based Learning. International Journal on Artificial Intelligence Tools, Vol. 11, No. 2, pp. 247-266
[29] O. Telelis and P. Stamatopoulos (2001). Combinatorial Optimization through Statistical Instance-Based Learning. Proceedings of the IEEE 13th International Conference on Tools with Artificial Intelligence ICTAI '01, pp. 203-209
[30] G. Boukeas, P. Stamatopoulos, C. Halatsis and V. Zissimopoulos (2004). Inherent Choice in the Search Space of Constraint Satisfaction Problem Instances. Proceedings of the 3rd Hellenic Conference on Artificial Intelligence SETN-2004, LNAI 3025, pp. 362-370
[31] G. Boukeas, C. Halatsis, V. Zissimopoulos and P. Stamatopoulos (2004). Measures of Intrinsic Hardness for Constraint Satisfaction Problem Instances. Proceedings of the 30th Conference on Current Trends in Theory and Practice of Computer Science SOFSEM 2004, LNCS 2932, pp. 184-195
[32] K. Hatzikokolakis, G. Boukeas and P. Stamatopoulos (2004). Construction and Repair: A Hybrid Approach to Search in CSPs. Proceedings of the 3rd Hellenic Conference on Artificial Intelligence SETN-2004, LNAI 3025, pp. 342-351
[33] I. Sakellariou and I. Vlahavas (2004). Distributed Singleton Consistency. Journal of Experimental and Theoretical Artificial Intelligence, Vol 16, Number 2, pp 107-124
[34] I. Sakellariou, I. Vlahavas, I. Futo, Z. Pasztor, and J. Szeredi (2006). Communicating Sequential Processes for Distributed Constraint Satisfaction, Information Sciences, Vol 176, Number 5, pp 490-521
[35] I. Sakellariou and I. Vlahavas (2004a). Simple Distributed Filtering on a CLP Platform. Companion Volume of 3rd Hellenic Conference on Artificial Intelligence, G. Vouros and T. Panagiotopoulos (eds), pp 318-327
3. PROPOSITIONAL SATISFIABILITY
The problem of Propositional or Boolean Satisfiability (SAT) is a special case of Constraint Satisfaction Problem, where all variable assume binary values (True/False), and the constraints are formulae of propositional logic, usually in some specific form called conjunctive normal form (CNF), where the formula is a conjunction of disjunctions. Each disjunct of a CNF formula is called clause. If each clause of a SAT instance has exactly k variable, then this is an instance of a k-SAT problem. It is well know that for k=2 the k-SAT problem (ie., the 2-SAT problem) can be solved in polynomial time, whereas for k≥ 3, it is NP-complete.
The SAT problem has been long researched in AI and Theoretical Computer Science. In Greece, the main body of research related to SAT, is being carried out by two groups, one at the University of Patras, headed by L. Kirousis, and the other one at the Athens University of Economics and Business, headed by A. Veneris.
University of Patras
At the University of Patras, L. Kirousis and his colleagues, address theoretical question concerning SAT. Part of their work focuses on the satisfiability threshold, or phase transition phenomenon: it has been observed empirically that there exists some specific value for the constraint-to-variables ratio of random k-SAT instances such that almost all instances with a lower ratio than this value are satisfiable, while almost all instances with a higher ratio are satisfiable. The theoretical study of this phase transition is a challenging problem that has received a lot of attention. In [5], the authors review the successive improvements of upper bounds for the 3-SAT threshold as well as the main techniques that have been employed for obtaining these improvements. The works [1,3,4] also concern the satisfiability threshold question for 3-SAT instances. More specifically, the authors present a greedy heuristic which at each step assigns true the literal with the maximum number of occurrences in the input instance. This algorithm implies a lower bound of 3.42 for the threshold value, and improved over the best previously known thus obtained lower bound of 3.26. A more sophisticated heuristic with a more complex literal selection rule achieves an improved lower bound of 3.52. One of the novelties of these heuristics was the utilization of information about the number of occurrences of literals in the input formula.
In [6], the authors obtain an upper bound of 4.571 for the unsatisfiability threshold value that improved the best previously known value of 4.596. Their approach combined the method of local satisfying truth assignments with probability estimates for the occupancy problem of random allocations of balls into bins.
A problem similar to the SAT problem that we discussed above is the minimal satisfiability problem, or Min-SAT. Loosely speaking, the problem here is to determine a truth assignment for the input formula that is minimal with respect to some partial order defined on the set of assignments. In [2], the authors investigate the complexity of minimal satisfiability of some generalized forms of propositional theories. More specifically, they obtain a dichotomy theorem for the Min-SAT problem, ie., a result that partition the set of possible instances to those that can be solved in polynomial time and those that are NP-complete. In this way they rule out the existence of problems of intermediate complexity. Moreover, [2] presented dichotomy results for some special cases of satisfiability problems that are related to propositional circumscription, as well as some simple conditions that tell apart polynomial-time solvable Min-SAT from NP-complete ones.
Athens University of Economics and Business
At the Athens University of Economics and Business (AUEB), the research group headed by A. Veneris is researching the applications of SAT in Electronic Design Automation (EDA). This work is partially supported by an EU Marie Curie Re-Integration grant. Recent years have seen an increased use of SAT-based tools in the design cycle for Very-Large-Scale-integration (VLSI) circuits. Design verification and model checking, test generation, logic optimization, and physical design, among other problems, have been successfully tackled with SAT-based solutions. This trend is due to recent advances in SAT solvers that make those engines efficient solution platforms for theoretically intractable problems previously difficult to solve with traditional methods. The use of SAT in the VLSI design cycle is strengthened by the amount of on going research into SAT solvers. Any improvement to the state-of-the-art in SAT solving immediately benefits all SAT-based solutions.
Although SAT-based solutions have been devised for most circuit-design problems, there had been no SAT solution for circuit debugging. Debugging occurs when a design/circuit fails verification or test. In error debugging, a design fails verification and a correction is needed in some location(s) to fix the error(s). In silicon debug, it is the silicon that fails test, and fault models are inserted in specific locations in the correct netlist to justify the failing behavior. In this manner, the test engineer can later cut the actual silicon in those locations to observe the actual sources of failure under a specialized microscope.
Debugging, also known as error/fault diagnosis, has been a 30 years old researched field with many algorithms and methodologies that use simulation and Binary Decision Diagrams (BDD). Nevertheless, their performance degrades exponentially as the number of error locations and the gate-count of the underlying design increases. In 2003 Veneris’ group work in ASPDAC introduced the first known algorithm that models debugging in terms of Boolean Satisfiability, an algorithm that later appeared in Trans. of CAD [7]. The prominence of this SAT-based debugging methodology when compared to previous simulation and BDD techniques comes from the fact of its scalability in terms of multiple errors and design size. The basic implementation of the algorithm was able to outperform by order of magnitude traditional techniques setting the stage for a new era in automation for design debugging.
Since then, a variety of different debugging algorithms were introduced. In [15], Quantified SAT [16] was utilized to provide further memory savings when debugging with multiple input vectors. The work of [8] uses the idea of maximum SAT, that is, the maximum set of satisfied clauses in a formula which is not satisfied, to improve run-time performance during debugging. More recently, [11] uses SAT to “compress” the erroneous test vector when a design failed, a process that makes existing debugging algorithms more scalable. SAT is also used in [14] to perform correction once the error location is found. Finally, the research in [9], introduces a novel methodology to model the sequential behavior of circuit over time, a formulation that provides major memory savings for existing debugging, test and verification algorithms. This work opens new avenues for novel techniques with Quantified Boolean Formula (QBF) Satisfiability with competitive performance when compared to SAT based techniques.
The group of A. Veneris has applied Boolean and pseudo-Boolean SAT [17] in the area of design for low-power. The research in [10] gives the first algorithm to estimate the maximum circuit activity. This method outperforms conventional simulation-based techniques in terms of performance and its accuracy. Earlier in [12], a SAT-based mapping algorithm for Field Programmable Field Arrays is proposed that it is able to map circuits in FPGAs not previously feasible.
Finally, the group pioneered the work on dedicated circuit-based SAT solvers. More specifically, in [13] we propose the first technique for SAT solvers to take advantage of the circuit don’t cares. In this manner, conventional solvers [18] can operate 3-5 times faster when the underlying CNF is a representation of some combinational digital circuitry.
References
[1]. A.C.Kaporis, L.M. Kirousis, and E.G. Lalas. The probabilistic analysis of a greedy satisfiability algorithm. Algorithms - ESA 2002, 10th Annual European Symposium, LNCS 2461, pp. 574-585, Rome, Italy, 2002.
[2]. L.M. Kirousis, and P.G. Kolaitis. The complexity of minimal satisfiability problems. Information & Computation, 187(1), pp. 20-39, 2003.
[3]. A.C. Kaporis, L.M. Kirousis, and E. Lalas. Selecting Complementary Pairs of Literals. Electronic Notes in Discrete Mathematics, 16, pp. 47-70, 2003.
[4]. A.C. Kaporis, L.M. Kirousis, and E.G. Lalas. The probabilistic analysis of a greedy satisfiability algorithm. Random Structures and Algorithms, 28(4), pp. 444-480, 2006.
[5]. L.M. Kirousis, Y.C. Stamatiou, and M. Zito. The unsatisfiability threshold conjecture: the techniques behind upper bound improvements. In: A.G. Percus, G. Istrate and C. Moore, eds., Computational Complexity and Statistical Physics, pp. 159-178, Oxford University, 2006.
[6]. A.C. Kaporis, L.M. Kirousis, Y.C. Stamatiou, M. Vamvakari, and M. Zito. The unsatisfiability threshold revisited. Discrete Applied Mathematics, 155(12), pp. !!!!!! 2007.
[7]. A.Smith, A.Veneris, M.F.Ali, and A.Viglas,“Fault diagnosis and logic debugging using Boolean satisfability.” IEEE Trans. on CAD, 24(10), pp.1606-1621, 2005.
[8]. S.Safarpour, M.Liffton, H.Mangassarian, A.Veneris and K.A.Sakallah, ``Improved Design Debugging Using Maximum Satisfiability.'' Formal Methods in CAD (FMCAD), 2007.
[9]. H.Mangassarian, A.Veneris, S.Safarpour, M.Benedetti and D.Smith, ``A Performance-Driven QBF-Based Iterative Logic Array Representation with Applications to Verification, Debug and Test.'' Int'l Conference on Computer-Aided Design (ICCAD), 2007.
[10]. H.Mangassarian, A.Veneris, S.Safarpour, F.N.Najm and M.S.Abadir, ``Maximum Circuit Activity Estimation Using Pseudo-Boolean Satisfiability,'' IEEE/ACM Design and Test in Europe Conference (DATE), 2007
[11]. S.Safarpour, A.Veneris and H. Mangassarian, ``Trace Compaction using SAT-based Reachability Analysis,'' IEEE/ACM Asian-South Pacific Design Automation Conference (ASPDAC), 2007
[12]. S.Safarpour, A.Veneris, G.Baeckler and R.Yuan, ``Efficient SAT-based Boolean Matching for FPGA Technology Mapping,'' IEEE/ACM Design Automation Conference (DAC), 2006
[13]. S.Safarpour, A.Veneris, R.Drechsler and J.Lee, ``Managing Don't Cares in Boolean Satisfiability,'' IEEE Design Automation and Test in Europe (DATE) Conference, 2004
[14]. Y.-S.Yang, S.Sinha, A.Veneris and R.K.Brayton, ``Automating Logic Rectification by Approximate SPFDs,'' IEEE/ACM Asian-South Pacific Design Automation Conference (ASPDAC), 2007
[15]. M.F.Ali, S.Safarpour, A.Veneris, M.S.Abadir and R.Drechsler, ``Post-Verification Debugging of Hierarchical Designs,'' IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 2005
[16]. M.Benedetti, “sKizzo:a suite to evaluate and certify QBFs,” Int’l Conf. on Automated Deduction, 2005, pp.369–376.
[17]. N.E´en and N.S¨orensson, “Translating pseudo-boolean constraints into SAT,” JSAT, Vol.2 pp.1-26, 2006
[18]. M.W.Moskewicz, C.F.Madigan, Y.Zhao, L.Zhang, and S.Malik ,“Chaff: engineering an efficient SAT solver,” Proceedings Design Automation Conference, 2001, pp.530–535.
4. EVOLUTIONARY ALGORITHMS
Evolutionary Algorithms (EA) are search methods that take their inspiration from natural selection and survival of the fittest in the biological word. In the Artificial Intelligence issue, they are generic population-based optimization algorithms. EAs differ from more traditional optimization methods in that they involve a search from a “population” of solutions (candidate solutions to the optimization problem), not from a single point. An initial population (coded candidate solutions initialized randomly) is evolved using some genetic operators inspired from biological evolution: selection, reproduction (crossover or recombination) and mutation. Each iteration of an EA involves a competitive selection that weeds out poor solutions that are evaluated by the cost (fitness) function, which is the environment within which the solutions “live”. Due to the use of the cost function, EAs perform a directed random search instead of a random search. Recombination (that swaps parts of a solution with another) redirects the search, while mutation makes a small change to a single element of a solution (individual). Thus, recombination and mutation are used to produce new solutions that are biased towards regions of the search space for which good solutions have been already found. The repeated evolution of the population probably approximates a (near) optimal solution, while the repetition can be stopped when a previously determined computational limit is reached.
Several different types of evolutionary search methods were developed independently. These include: Genetic Algorithms (GA), Genetic Programming (GP), Evolutionary Programming (EP) and Evolutionary Strategies (ES). These are similar techniques that differ in the coding used, the implementation details and the nature of the particular applied problem. More specifically:
- Genetic Algorithms are using (traditionally) binary coding for the candidate solutions and apply selection, recombination (with a relative high probability) and mutation. These type of EAs focuses on optimizing general combinatorial problems.
- Genetic Programming which evolves a population of computer programs. The fitness is determined by the ability of each program to solve a computational problem.
- Evolutionary Programming, which focuses on optimizing continuous functions with recombination (like GP, only the structure of the program is fixed and its numerical parameters are allowed to evolve).
- Evolution Strategieswhich focuses on optimizing functions without recombination (the representation of the solutions are vectors of real numbers and uses self-adaptive mutation rates).
The different variations of EAs have been successfully applied to a variety of search and optimization, benchmarks (such as TSP and Knapsack) as well as real world problems. Some indicative real world applications are: engineering design, image and signal processing, scheduling and transportation problems, parameter fitting, prediction, data and knowledge mining, e.t.c. Although, the initial formulation of EAs considered their application to unconstrained problems, recently a variety of methods have been proposed for handling constrains.
Other Related Techniques include Differential Evolution (DE) which is based on vector differences and is suited for numerical optimization, Particle Swarm Optimization (PSO), which is inspired from animal flocking behavior and is suited for numerical optimization, Ant Colony Optimization (ACO), which is inspired from ant foraging by pheromone communication to form path and is suited for combinatorial optimization problems, and Memetic Algorithms (MA) that simulate the social behavior instead of biological behavior.
In the past few years research on EAs has been carried out, mainly but not exclusively, at the following academic departments in Greece: Department of Computer Engineering and Informatics at the University of Patras joint with the Department of Information and Communication Systems Engineering at the University of the Aegean, Department of Mathematics at the University of Patras and Department of Business Administration at the University of Patras.
University of Patras
Department of Computer Engineering and Informatics
Research on developing new EAs, have been carried out in the Pattern Recognition Laboratory (PR-Lab) of the Department of Computer Engineering & Informatics (Professor S. Likothanassis ), jointly with the Department of Information and Communication Systems Engineering of the University of the Aegean (Professor S. Katsikas ). This new EA has been designed to explore the whole space of the candidate models, in any system identification problem, modeled in the state space. New specific genetic operators were designed in order to handle complex data structures (like matrices, with real elements) and a probabilistic fitness function was used for the first time. The implementation of this EA was used to integrate to Multi Model Partitioning Theory of Lainiotis (MMP). The MMP is used to identify the correct model between a set of candidate models that optimally fits to the data. Although this method is consistent and works very successfully, even in non stationary environments, its disadvantage was the sensitiveness in the selection of the initial candidate models. By the use of the new EA, this disadvantage was alleviated by initializing randomly a population of candidate models that are evolved according their fitness, which is the a posteriori probability for each specific model to be the true model. In this way, the whole model space is explored and finally the correct model is exploited. The new MMP-EA is data-driven and has the ability to perform a global search of the whole model space and is independent of the data noise distribution. Furthermore, it can identify the model’s order and can follow the model’s structure changes [1],[2]. This new evolutionary method has been applied in a variety of real world applications, such as: Evolutionary AR, ARMA and ARX model identification with unknown model order [3], [4], evolutionary time series prediction [5], evolutionary system identification for non-linear systems [6].
Hybrid Genetic Algorithms and Applications, is an area where the PR-Lab has performed significant research work, both in developing new algorithms and applying them in real word problems. The field of Neural Network (NN) training, is still an open problem, although a variety of training algorithms have been presented. This is a global search problem, where an optimization algorithm has to find the optimal combination of a set of weights that minimizes the error function. Furthermore, in order to apply the traditional training algorithms one has to suppose a fixed NN’s structure (concerning the internal-hidden layers). Thus, the problem is twofold: one has first to determine the optimal NN’s structure and then to train the network to fit the training data. In order to face this problem, a new evolutionary algorithm has been proposed that evolves a population of NN individuals, of different structure, while simultaneously it trains the new individuals, for some epochs, by assigning random values (in a predefined interval), to the weights. Then, the trained individuals are evaluated, concerning the minimization of the output error, as well as structure’s complexity. After a termination criterion has been satisfied, the resulting Evolutionary NN, is optimized both in learning the training data as well as in the structure [7], [8]. Other minimization criteria (like training time complexity) can be incorporated to the fitness function, in order to improve the NN’s performance. This evolutionary algorithm has been extended to evolve the input layer, as well as the hidden layers, and has been applied to a variety of real worlds problems, such as: exchange rate forecasting (where, except of the evolution of the hidden weights, the evolution of the inputs is considered) and time series prediction [9], biosignal modeling and prediction ( Magneto Cardiogram - MCG, Magneto Encephalogram –MEG of epileptic patients, fetal MCG) [10] - [15]. In these applications, since the row data are modeled by time series, the main problem is to identify the number of the past values needed (the model order). The proposed algorithms can extract this information automatically, by identifying the correct model order and then the model’s parameters.
Other EA applications: A Genetic Programming based technique for non linear model structure identification of complex biomedical data is proposed in [16], the application of evolutionary computation to the school timetabling problem (solving a conditions satisfaction problem with GAs) is referred [17], [18] and the integration of evolutionary techniques and agents’ technology in E-learning Environments (user profile optimization) is addressed in [19], [20].
Department of Mathematics
Research on other related techniques has been carried out at the Computational Intelligence Laboratory – CILab (Professor M. Vrahatis ) .
Particle Swarm Optimization (PSO): CILab's research has focused on the development of new Particle Swarm Optimization (PSO) variants for numerical optimization problems, which can handle the exploration-exploitation problem effectively. Its work focused on different types of optimization problems, including unconstrained, constrained, noisy, dynamic, multiobjective and discrete problems, developing more efficient variants of established algorithms. Three major new variants have been developed and introduced, namely Unified PSO(UPSO) [23], Memetic PSO (MPSO) [22], and Vector Evaluated PSO(VEPSO) [21]. UPSO is an extension of the standard PSO that harnesses the local and the global variant of PSO into a single method that combines their behavior and convergence properties. Convergence in probability was proved for UPSO and different swarm-level and particle-level schemes for selecting its parameters have been evaluated. MPSO incorporates a local search component in the PSO mechanism. This component is proved very useful in cases where further local refinement of the already detected solutions is required, e.g., in cases where high accuracy of the detected solutions is desirable. The MPSO scheme has also been proved to converge in probability. VEPSO is a multi-swarm scheme for tackling multi-objective problems, with extensive parallelization capabilities. All the aforementioned approaches have been applied successfully on a plethora of applications that involve single- and multi-objective problems, integer and mixed-integer problems, as well as dynamic and noisy benchmark problems and real-life applications. Finally, a general framework based on computational statistics has been proposed for the design and analysis of evolutionary and swarm intelligence algorithms [24].
Differential Evolution (DE): Differential Evolution has been extensively researched and parallelized [25] in an attempt to increase its performance. Moreover, DE is used as a training method for various types of Artificial Neural Networks (ANN), such as ANNs with integer weights [26]. This approach has been parallelized in [27]. In addition, the combination of Evolutionary Algorithms (EA) with clustering has allowed the simultaneous computation of local and global minima [28]. DE was also used to address the problem of very high dimensionality problems, such as forming subsets of predictive genes in microarray data [29]. More specifically, a DE algorithm creates gene subsets and its fitness function is based on the performance of an ANN [30]. Moreover, a new DE-based scheme for optimization with multistart trajectory-based optimization methods was developed, improving significantly the established approaches [31]. Finally, Genetic Algorithms such as Genetic Programming has been engaged in order to develop novel DE operators [32]. Furthermore, in order to enhance the performance of evolutionary clustering algorithms, the laboratory has developed a new density function, named Window Density Function (WDF) [33].
Techniques for enhanced performance:In single-objective optimization problems CILab has introduced and worked on two techniques, called Deflection and Stretching [34], in combination with PSO and DE to alleviate convergence to local minima by transforming the original objective function after the detection of a minimizer [35, 21, 36]. The effect of Deflection is rather local around the point of application, while Stretching has a wider impact on the original function, eliminating all minimizers with higher value than the detected one. The aforementioned approaches were shown to be very useful on different applications were a multitude of minimizers is required [35, 21, 36, 37, 38].
Memetic Algorithms (MA): Besides the research on using Memetic Algorthims (MA) in order to improve the performance of PSO, MA were used, combined with deterministic and stochastic processes, in order to improve the performance of DE algorithms. The convergence of MA was also considered. The combination of the MA techniques proposed, has been successfully applied on a variety of problems in Complex and Nonlinear Systems and Optimization [39, 47].
Applications: CILab has also developed new approaches of the aforementioned algorithms and applied them on a wide range of applications in Operations Research, Engineering Control and Design, Astronomy and Bioinformatics. A major application field has been the detection of periodic orbits of nonlinear mappings and 3D galactic potentials [38, 40], where MPSO, PSO and MA have been applied with very promising results. Also, PSO was applied for training probabilistic neural networks for data classification in bioinformatics and DE for on-line learning for colonoscopic diagnosis [41]. The optimization of fuzzy simulation modelling systems constituted another important field of application, where the proposed algorithms outperformed different evolutionary approaches [37, 42]. Furthermore, PSO and DE have been used in Cryptanalysis [43]. The results indicate that the proposed approach is very promising. Finally, the performance of the algorithms has been studied with very promising results in different optimization and operations research problems [21, 44, 45, 22] as well as financial time series modelling [46].
Department of Business Administration
Andreas Nearchou’s ) research work is associated with nature-inspired computing for robotics and production management. His research conducted on about 16 years has produced various novel evolutionary models for solving intractable combinatorial optimization problems such as robot motion planning, vehicle routing and scheduling, jobs sequencing, assembly line balancing, and machine layout design. A selected part of his contributions is shortly highlighted below.
Robot motion planning (RMP): RMP is a fundamental theme in the development of autonomous robots defined as follows: How can a robot decide what motions to perform in order to move from an initial location to a desired final without colliding with the obstacles in its environment? RMP is PSPACE-hard. Previous works were usually limited to RMP of a point-robot moving in static environments and manipulators with non-redundant degrees of freedom. Nearchou examined RMP under the framework of genetic and evolutionary algorithms (GEAs) for the case of mobile robots navigating in hazardous dynamic environments [48], and for the case of redundant robot manipulators operating in complex production cells [49,50]. Some of the developed GEAs were tested with success on real-world industrial robots.
Assembly line balancing problem (ALBP): ALBP is a decision problem arising when an assembly line is to be configured or redesigned and consists of determining the optimal partitioning (balancing) of the assembly work among the workstations while optimizing one or more objectives without violating the restrictions imposed on the line. Any variant of ALBP is NP-hard. Traditional OR techniques (e.g. branch-and-bound and dynamic programming) can only solve small to medium size ALBPs. Nearchou [51,52] investigated the use of differential evolution (DE) (one of the latest version of GEA) for solving the Type 2 single model ALBP (SALBP-2) with multiple-objectives. This was the first attempt to solve ALBP via DE. The results obtained were very promising. DE was found superior (in regard to the quality of the solutions obtained) to other heuristics including the genetic algorithms.
Job sequencing and scheduling: Nearchou examined well-known intractable scheduling problems, including the single machine sequencing problem [53], the n-machines flow-shop sequencing problem [54], and the common due date (CDD) scheduling problem [55]. New approximate algorithms were developed and their performance was analyzed and examined over large size instances of public available benchmarks. It is worth pointing out that in the case of CDD problem, Nearchou developed a special DE algorithm which was found able to introduce new upper bounds to nearly 60% of the existing benchmarks instances which include up to 1000 jobs to be scheduled.
Machine layout design: An important factor in designing a flexible manufacturing system (FMS) is the determination of an effective layout of the machines in the shop floor so that to provide efficient operation. This layout has a significant impact to the material handling cost, the time of processing, the throughput of the production system, and therefore affects the overall productivity of the FMS. The loop layout design problem (LLDP) arises when the machines in a FMS are arranged in a closed ring-like network and the materials are transported around this network in only one direction. LLDP is NP-hard. Nearchou [56] introduces a DE algorithm for the solution of LLDP which was found superior to existing in the related literature heuristics.
References
[1 ] K. G. Berketis, S.K. Katsikas, and S. D. Likothanassis, “Multi Model Partitioning Filters and Genetic Algorithms”, Journal of Non-Linear Analysis: Theory, Methods and Applications, vol.30, No 4, pp. 2421-2447, 1997.
[2 ] S. Katsikas, S. Likothanassis, G. Beligiannis, K. Berketis and D. Fotakis, “Genetically Determined Variable Structure Multiple Model Estimation”, IEEE Signal Processing, Vol. 49, No. 10, pp. 2253 -2261, October 2001.
[3 ] G. Beligiannis, E. Demiris and S. Likothanassis, ‘Self-Adaptive Evolution Strategies for ARMA Model Identification’, X European Signal Processing Conference (EUSIPCO-2000), Tampere, Finland, September 5-8, 2000.
[4 ] G. Beligiannis, E. Demiris and S. Likothanassis, ‘Self-Adaptive Evolution Strategies for ARMA Model Identification’, X European Signal Processing Conference (EUSIPCO-2000), Tampere, Finland, September 5-8, 2000.
[5 ] G. Beligiannis, S. Likothanassis and L. Skarlas, “Evolutionary Multi-Model Estimators for ARMA System Modeling and Time Series Prediction”, 7th International Work Conference on Artificial and Natural Neural Networks (IWANN2003), Mahon, Menorca (Balearic Islands), Spain, 2003.
[6] N. Beligiannis, E. N. Demiris and S. D. Likothanassis, "Evolutionary Multi Model Partitioning Filters for Non-Linear Systems", Genetic and Evolutionary Computation Conference (GECCO’99), Orlando, Florida USA, July 14-17, 1999.
[7] S. Likothanassis, E. Georgopoulos, and A. Adamopoulos, ”Structure Determination and Training of Neural Networks Using Evolution Programs”, Neural, Parallel and Scientific Computations Journal, Vol. 8, pp.29-48, 2000.
[8] E. Georgopoulos, S. Likothanassis and A. Adamopoulos, “Evolving Artificial Neural Networks Using Genetic Algorithms’’, Journal of Neural Network World, V. 4, pp.565-574, 2000.
[9] A. Andreou, E. Georgopoulos, and S. Likothanassis, “Exchange Rates Forecasting: A Hybrid Algorithm Based On Genetically Optimized Adaptive Neural Networks”, Computational Economics Journal, Kluwer Academic Press, Vol. 20 (3), pp. 191-210, December 2002.
[10] E. Georgopoulos, A. Adamopoulos and S. Likothanassis and H. Antonopoulou, ‘Human MCG Modeling Using Evolutionary Artificial Neural Networks’, 1st IEEE Symposium on Combinations of Evolutionary Computation and Neural Networks (ECNN 2000), in the 9th IEEE International Conference on Fuzzy Systems, San Antonio, Texas, USA, May 11-12, 2000.
[11] A. Adamopoulos, E. Demiris, S. Likothanassis, G. Beligiannis and P. Anninos, “Evolutionary Multimodel Analysis of Fetal Magnetocardiogram”, Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems – EUROGEN 2001, Athens, September 19-21, 2001.
[12] A. Adamopoulos, P. Anninos, S. Likothanassis, E. Georgopoulos and G. Beligiannis, “Genetically Optimized Multi-Layered Perceptrons for the Prediction of Biomagnetic Signals”, Neural Networks and Expert Systems in Medicine and Healthcare (NNESMED 2001), Milos, Greece, June 20-22, 2001.
[13] A. V. Adamopoulos, P. A. Anninos, S .D. Likothanassis, G. N. Beligiannis and L. V. Skarlas and E .N. Demiris, “Evolutionary Self-adaptive Multimodel Prediction Algorithms of the Fetal Magnetocardiogram”, 14th International Conference on Digital Signal Processing (DSP 2002), Santorini, Greece, 1-3 July, 2002.
[14] E.F. Georgopoulos, A.V. Adamopoulos, S.D. Likothanassis: “Modeling the magnetoencephalogram of epileptic patients using genetic programming”,Proceedings of Numerical Analysis 2007 Conference (NumAn 2007), pp. 68 – 71, Kalamata, September 3 – 7 , 2007.
[15] S. Likothanassis, K. Perdokuri, L. Skarlas and A. Tsakalidis, “Evolutionary Biomedical Signal Processing Techniques”, Measurement Science Review Journal, Vol. 4, (2), pp. 15-19, 2004.
[16] G. N. Beligiannis, L. V. Skarlas, S. D. Likothanassis and K. Perdikouri, “Nonlinear Model Structure Identification of Complex Biomedical Data Using a Genetic Programming Based Technique”, IEEE Transactions on Instrumentation and Measurement, Vol. 54, No.6, pp.2184-2190, 2005.
[17] Grigorios N. Beligiannis, Charalampos N. Moschopoulos, Georgios P. Kaperonis and Spiridon D. Likothanassis, “Applying evolutionary computation to the school timetabling problem: The Greek case”, Computers & Operations Research Journal, In Press, Elsevier Science, Vol. 35, pp. 1265-1280, 2008.
[18] Grigorios N. Beligiannis, Charalampos N. Moschopoulos and Spiridon D. Likothanassis, “A Genetic Algorithm Approach to School Timetabling”, Journal of the Operational Research Society, accepted for publication, 2008.
[19] Konstantinos C. Giotopoulos, Christos E. Alexakos, Grigorios N. Beligiannis and Spiridon D. Likothanassis, “Integrating Computational Intelligence Techniques and Assessment Agents in E-Learning Environments”, International Journal of Computational Intelligence, Volume 3 Number 4, 2006, pp 328-337.
[20] K. Giotopoulos, C. Alexakos, G. Beligiannis and S. Likothanassis, “Computational Intelligence Techniques and Agents’ Technology in E-learning Environments”, International Journal of Information Technology, Vo.2, No. 2, pp. 147-156, 2006.
[21] Parsopoulos K.E. and Vrahatis M.N., Recent Approaches to Global Optimization Problems Through Particle Swarm Optimization, Natural Computing, vol. 1, no. 2-3, pp. 235-306, Springer, 2002.
[22] Petalas Y.G., Parsopoulos K.E. and Vrahatis M.N., Memetic Particle Swarm Optimization, Annals of Operations Research, vol. 156, no. 1, pp. 99-127, Springer, 2007.
[23] Parsopoulos K.E. and Vrahatis M.N., Parameter Selection and Adaptation in Unified Particle Swarm Optimization, Mathematical and Computer Modelling, vol. 46, no 1-2, pp. 198-213, Elsevier, 2007.
[24] Bartz-Beielstein T., Parsopoulos K.E. and Vrahatis M.N., Design and Analysis of Optimization Algorithms Using Computational Statistics, Applied Numerical Analysis and Computational Mathematics, vol. 1, no. 2, pp. 413-433, Wiley, 2004.
[25] Tasoulis D.K., Pavlidis N.G., Plagianakos V.P. and Vrahatis M.N., Parallel Differential Evolution, In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2004), Portland, Oregon, U.S.A., vol. 2, pp.2023-2029, IEEE 2004.
[26] Plagianakos V.P., Magoulas G.D. and Vrahatis M.N., Evolutionary Training of Hardware Realizable Multilayer Perceptrons, Neural Computing and Application, vol. 15, pp. 33-40, 2005.
[27] Plagianakos V.P. and Vrahatis M.N., Parallel Evolutionary Training Algorithms for `Hardware-Friendly' Neural Networks, Natural Computing, vol. 1, pp. 307-322, Springer, 2002.
[28] Tasoulis D.K., Plagianakos V.P. and Vrahatis M.N., Clustering in Evolutionary Algorithms to Efficiently Compute Simultaneously Local and Global Minima, In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2005), Edinburgh, UK, vol. 2, pp. 1847-1854, IEEE 2005.
[29] Tasoulis D.K., Plagianakos V.P. and Vrahatis M.N., Computational Intelligence Algorithms and DNA Microarrays,In: Computational Intelligence in Bioinformatics, A. Kelemen, A. Abraham and Y.-H. Chen, (Eds.), Studies in Computational Intelligence (SCI), vol. 94, Chapter 1, pp. 1-31, Springer-Verlag, Berlin, 2008.
[30] Tasoulis D.K., Plagianakos V.P. and Vrahatis M.N., Differential Evolution Algorithms for Finding Predictive Gene Subsets in Microarray Data, In: Artificial Intelligence Applications and Innovations, IFIP International Federation for Information Processing, I. Maglogiannis, K. Karpouzis and M. Bramer (Eds.), vol. 204, pp. 484-491, Springer, Boston, U.S.A., August 2006.
[31] Laskari E.C., Parsopoulos K.E. and Vrahatis M.N., Evolutionary Operators in Global Optimization with Dynamic Search Trajectories, Numerical Algorithms, vol. 34, no 2-4, pp. 393-403, Springer, 2003.
[32] Pavlidis N.G., Tasoulis D.K., Plagianakos V.P. and Vrahatis M.N., Human Designed Vs. Genetically Programmed Differential Evolution Operators, In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2006), Vancouver, Canada, pp. 1880-1886, IEEE 2006.
[33] Tasoulis D.K. and Vrahatis M.N., The new window density function for efficient evolutionary unsupervised clustering, In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2005), Edinburgh, UK, vol. 3, pp. 2388-2394, IEEE 2005.
[34] Magoulas G.D., Vrahatis M.N. and Androulakis G.S., On the Alleviation of the Problem of Local Minima in Backpropagation, Nonlinear Analysis, Theory, Methods and Applications, vol. 30, no 7, pp. 4545-4550, Elsevier, 1997.
[35] Parsopoulos K.E., Plagianakos V.P., Magoulas G.D. and Vrahatis M.N., Objective Function “Stretching” to Alleviate Convergence to Local Minima, Nonlinear Analysis, Theory, Methods and Applications, vol. 47, no 5, pp. 3419-3424, Elsevier, 2001.
[36] Parsopoulos K.E. and Vrahatis M.N., On the Computation of All Global Minimizers Through Particle Swarm Optimization, IEEE Transactions on Evolutionary Computation, vol. 8, no 3, pp. 211-224, IEEE, 2004.
[37] Papageorgiou E.I., Parsopoulos K.E., Stylios C.D., Groumpos P.P. and Vrahatis M.N., Fuzzy Cognitive Maps Learning Using Particle Swarm Optimization, Journal of Intelligent Information Systems, vol. 25, no 1, pp. 95-121, Springer, 2005.
[38] Skokos Ch., Parsopoulos K.E., Patsis P.A. and Vrahatis M.N., Particle Swarm Optimization: An Efficient Μethod for Tracing Periodic Orbits in 3D Galactic Potentials, Monthly Notices of the Royal Astronomical Society, vol. 359, pp. 251-260, Blackwell Publishing, 2005.
[39] Antonopoulos C.G., Petalas Y.G., Bountis T.C. and Vrahatis M.N., Estimation of Dynamic Aperture of Symplectic Maps using Evolutionary Algorithms, In Proceedings of the 18th Summer School and Conference “Order and Chaos”, Volos, Greece, T.C. Bountis, (Ed.), in Greek, 2006.
[40] Petalas Y.G., Parsopoulos K.E. and Vrahatis M.N, Stochastic Optimization for Detecting Periodic Orbits of Nonlinear Mappings, Nonlinear Phenomena in Complex Systems, accepted for publication, 2008.
[41] Magoulas G.D., Plagianakos V.P. and Vrahatis M.N., Neural network-based colonoscopic diagnosis using on-line learning and differential evolution, Applied Soft Computing, vol. 4, 369-379, 2004.
[42] Petalas Y.G., Parsopoulos K.E. and Vrahatis M.N, Improving Fuzzy Cognitive Maps Learning through Memetic Particle Swarm Optimization, Soft Computing, accepted for publication, 2008.
[43] Laskari E.C., Meletiou G.C., Stamatiou Y.C. and Vrahatis M.N.,Evolutionary Computation Based Cryptanalysis: A First Study, Applied Mathematics and Computation, pp. 823-830, 2005.
[44] Pavlidis N.G., Parsopoulos K.E. and Vrahatis M.N., Computing Nash Equilibria Through Computational Intelligence Methods, Journal of Computational and Applied Mathematics, vol. 175, pp. 113-136, Elsevier, 2005.
[45] Georgiou V.L., Pavlidis N.G., Parsopoulos K.E., Alevizos Ph.D. and Vrahatis M.N., New Self-Adaptive Probabilistic Neural Networks in Bioinformatic and Medical Tasks, International Journal on Artificial Intelligence Tools, vol. 15, no. 3, pp. 371-396, World Scientific, 2006.
[46] Pavlidis N.G., Tasoulis D.K., Plagianakos V.P. and Vrahatis M.N., Computational Intelligence Methods for Financial Time Series Modeling, International Journal of Bifurcation and Chaos, vol. 16, pp.2053-2062, 2006.
[47] Petalas Y.G., Antonopoulos C.G., Bountis T.C and Vrahatis M.N., Detecting Resonances using Evolutionary Algorithms, Proceedings of the International Conference of “Computational Methods in Sciences and Engineering” (ICCMSE 2006), 2006.
[48] Nearchou A., “Adaptive Navigation of Autonomous Vehicles using Evolutionary Algorithms”, Journal of Artificial Intelligence in Engineering, 13/2, 159-173, 1999.
[49] Nearchou A. and Aspragathos N., “A Genetic Path Planning Algorithm for Redundant Articulated Robots”. ROBOTICA, 15, 213-224, 1997.
[50] Nearchou A., “Solving the Inverse Kinematics Problem of Redundant Robots Operating in Complex Environments via a Modified Genetic Algorithm”. Journal of Mechanism and Machine Theory, 33/3, 273-292, 1998.
[51] Nearchou A. “Balancing large assembly lines by a new heuristic based on differential evolution method”, Int. Journal of Advanced Manufacturing Technology, 34, 1016-1029, 2007.
[52] Nearchou A. “Multi-objective balancing of assembly lines by population heuristics²,Int. Journal of Production Research. 46/8, 2275 –2297, 2008.
[53] Nearchou A. and Omirou S., “Differential evolution for sequencing and scheduling optimization²,Journal of Heuristics 12/6, 395-411, 2006.
[54] Nearchou A., "The effect of various operators on the genetic search for large scheduling problems ". Int. Journal of Production Economics, 88/2, 191-203, 2004.
[55] Nearchou A. “A differential evolution approach for the common due date early/tardy job scheduling problem²,Computers & Operations Research, 35, 1329-1343, 2008.
[56] Nearchou A. ²Meta-heuristics from nature for the loop layout design problem²,Int. Journal of Production Economics, 101/2 , 312-328, 2006.
5. CLOSURE & REMARKS
We have tried to briefly summarize the contributions of the Greek AI community to search and constraint satisfaction. These important areas of AI perhaps have not received as wide attention by the community as other areas, such as learning for example. However, significant contributions have been made by the research groups that are working on search and constraints. We have to note that we have only tried to cover the work of researchers who, at least partly, publish in AI venues. There is a large body of research by Greek scientists working in areas such as Operations Research and Theoretical Computer Science that is relevant to search and constraints (specifically combinatorial optimization) but has been developed outside the AI community and, hence, has not been covered.
ACKNOWLEDGEMENTS
We would like to thank all the researchers who contributed to this chapter. Especially, thanks to Ilias Sakellariou for his help in compiling the sub-chapter on constraint satisfaction.