next up previous contents
Next: 1 Requirements of Search Up: 2 Search, Evolutionary Algorithms Previous: 2 Search, Evolutionary Algorithms   Contents

1 Problem Solving and Search

Most human activity can be defined as a form of complex problem solving. Thus, problem solving by a computer program is considered to be an instance of artificial intelligence, where the task consists of managing information and searching for solutions [Shapiro, 1990]. Given a representation of a problem and a description of an ideal solution, the goal of search is to find a solution equal to or close to the ideal solution. In many cases, decision making and problem solving are formulated as optimisation problems [Pardalos and Resende, 2002]. The role of the search method is to find the best solution among possible alternatives, optimising for solution quality.

An example of problem solving in artificial intelligence is the field of automatic programming [Barr et al., 1989]. Computers perform calculations by means of programs. Designing and writing programs can be tedious and difficult. Given a specification of the desired behaviour of a program, it would be desirable if another program could automatically generate a solution that met the specification. Although not normally considered an artifact of artificial intelligence, compilers were an early form of automatic programming as they allowed programmers to write an algorithm in a high-level language that was then interpreted and compiled into the lowel-level machine code used by the computer's processor. Later, while investigating the possibility of learning machines, Friedberg (1958) designed an algorithm that was able to evaluate the quality of a computer program, make random changes to it and then re-test for improvements. Since then, many advances have been made in the field of artificial intelligence and automatic programming. For a further discussion of automatic programming see [Barr et al., 1989].

Another example of problem solving by computer programs can be seen in the field of operational research. Real-world problems are routinely solved efficiently and accurately by means of computer programs [Pardalos and Resende, 2002]. Operational research is concerned with studying such methods and their applications. The methods developed in the cross-disciplinary research between operational research and artificial intelligence are typically considered to be the state-of-the-art applied algorithms, as they produce the solutions that are used in everyday decision making.



Subsections
next up previous contents
Next: 1 Requirements of Search Up: 2 Search, Evolutionary Algorithms Previous: 2 Search, Evolutionary Algorithms   Contents
S Gustafson 2004-05-20