Powered by

# Problems To Be Solved

Field of evolutionary computing is primarily concerned with problem solvers

# Optimisation, Modelling and Simulation Problems

  • Classification of problems is based on a black box model of computer systems
    • The system takes some input, processes it through some model whose details are not specified (hence black box)
    • The purpose of this model is to represent some aspects of the world relevant to the particular application.
    • Ex - a statistical tool estimating the likelihood of rain given some meteorological input data.
    • In essence, the black box view of systems distinguishes three components, the input, the model, and the output.

# Optimisation

  • In an optimisation problem the model is known, together with the desired output or a description thereof, and the task is to find the input leading to this output.
    • For example, in Travelling Salesman Problem, the formula is the model, the cities are the inputs and the shortest path to be found is the output. Rather specifying the exact length, it is required that the tour should be shorter than all others. (output is defined implicitly)
    • In 8 queens, the output is specified explicitly - OK or not OK.
  • ![[Pasted image 20240225013328.png]]

# Modelling

  • In a modelling or system identification problem, corresponding sets of inputs and outputs are known, and a model of the system is sought that delivers the correct output for each known input.
  • This corresponds to finding a model of the world that matches our previous experience, and can hopefully generalise to as-yet unseen examples.
  • ![[Pasted image 20240225013621.png]]
  • Modelling problems can be transformed into optimisation problems. The general trick is to designate the error rate of a model as the quantity to be minimised or its hit rate to be maximised.
    • For a segmentation problem, given a set of models M that can be applied to the problem, the set of inputs is M and the output for a given m \in M is an integer saying how many images were correctly labelled by m.

# Simulation

  • In a simulation problem we know the system model and some inputs, and need to compute the outputs corresponding to these inputs.
  • Simulation can be more economical than studying the real-world effects.
  • Simulation can be the tool that allows us to look into the future, as in weather forecast systems.
  • ![[Pasted image 20240225014133.png]]

# Search Problems

  • An assumption about black box systems is that the model is directional and cannot be simply inverted. Hence, solving an optimization/modelling problem requires identification of a particular object in a space of possibilities.
  • The process of problem solving can be viewed as a search through a potentially huge set of possibilities to find the desired solution. Consequently, the problems that are to be solved this way can be seen as search problems.
  • This view leads to the concept of a search space, being the collection of all objects of interest including the solution we are seeking.
  • The specification of the search space is the first step in defining a search problem. The second step is the definition of a solution.
    • For optimization, it can be a explicit or implicit definition (shortest of all lengths) and for modelling, it is defined as number of inputs for which correct output is obtained is maximal.

# Optimisation Versus Constraint Satisfaction

  • Objective function is some way of assigning a value to a possible solution that reflects its quality on a scale
  • Constraint represents a binary evaluation telling us whether a given requirement holds or not
  • Problems can include both/one of these and this leads to the table - ![[Pasted image 20240303202920.png]]
    • TSP is a FOP
    • 8 Queens is a CSP
  • Constraint Satisfaction problems can be transformed into Optimization problems similar to how we transform modelling into optimization. Rather than requiring perfection, we just count the number of satisfied constraints and introduce this as an objective function to be maximised.
  • A vague description of a problem has to be converted into the above to solve it.

# NP Problems

  • If the search space S is defined by continuous variables, then we have a numerical optimisation problem.
  • If S is defined by discrete variables (e.g., Booleans or integers), then we have a combinatorial optimisation problem.
    • Discrete search spaces are always finite or, in the worst case, countably infinite
  • Notions of computational complexity
    • Problem size - Involves dimensionality of the problem and problem variables.
    • Running time - Number of elementary steps, or operations, it takes to terminate.
      • The best-known definitions of problem are expressed by a formula that specifies an upper-bound for the worst-case running-time as a function of the problem size.
    • Problem reduction - Transform one problem into another via a suitable mapping
  • Classes of complexity
    • P - There exists an algorithm that can solve it in polynomial time
    • NP - Can be solved by some algorithm (with no claims about its run-time) and any solution can be verified within polynomial time by some other algorithm.
    • NP-complete - Belongs to the class NP and any other problem in NP can be reduced to this problem by an algorithm which runs in polynomial time.
    • NP-hard - It is at least as hard as any problem in NP-complete but where the solutions cannot necessarily be verified within polynomial time.
  • ![[Pasted image 20240303204203.png]]