实用算法-poad笔记

• performance indicators
  • two key parameter
    • solution quality reached after a certain runtime
    • ruantime to reach a certain solution quality
  • measuer data samples A containing the results from multiple runs and eatimate key parameters
• absolute runtime
  • measure the (absolute) consumed runtime of the algorithm in ms
    • advantages:
      • results in many works reported in this format
      • a quantity that makes physical sense
      • includes all "hidden complexities" of algorithm
    • disagvantages
      • strongly machine dependent
      • granularity of about 10ms:many things seem to happen at the same time
      • can be biased by “outside effects",eg..,OS,scheduling,other processes,I/O,swapping
      • inherentyly incomparble
  • hardware,software,os,etc.all have nothing to do with the optimization algorithm itself and are relevant only in a specific application...
• function evaluations:FEs
  • measure the number of fully constructed and tested candidate solutions
    • advantages:
      • results in many works reported in this format(or fes can be deduced)
      • machine-independent measure
      • cannot be influenced by "outside effects"
      • in many optimization problems,computing the objective value is the most time consuming task
    • disadvantages:
      • no clear relationship to real runtime
      • does not contain "hidden complexities" of algorithm
      • 1 FE:very different costs in different situations!
    • relevant for comparing algorithms,but not so much for the practical application
• runtime
  • rewrite the two key parameters by choosing a time messure
    • solution quality reached after a certain number of FEs
    • number FEs needed to reach a certain solution quality
• solution quality
  • common measure of solution quality:objective function value of best solution discoved.
  • rewrite the two key parameters
    • best objective funcion value reached afer a certain number of FEs
    • number FEs needed to reach a certain objective function value .
• determining target values
  • how to determine the right maximum FEs or target function values?
    • from studies in literature regarding similar or the same problem.
    • from experience .
    • from prior ,small-scale experiments.
    • based on known lower bounds.

1. arithmetic mean:
   1. The arithmetic mean a is an estimate of the expected value. It is computed as the sum of all elements in the sample data A divided by the total number of values.
2. median
   1. the median med(X) is the value right in the Middle of a sample or distribution ,dividing it into two equal halves.
   2. for a sorted data sample A,index starting at 0;
3. when describing a random process ,we should always use the median instead of the mean.
4. standard deviation .
5. quantiles.
   1. 
   2. Like the mean ,presenting the standard deviation often implicitly assumes a symmetric distribution .And it maybe misleading in skewed distribution .
   3. better use quartiles or higher quantiles to describe such an area.
   4. quantiles are robust against outliers and skew distributions ,

we can now perform 20 runs each with two different optimization algorithm on one problem and compute the median of one of the two perform measure .

if we say "A is better than B",we have a certain α to be wrong .The statement "A is better than B" makes only sense if we can geive an upper bound α for than error probability .

Compare two data samples A = (a1, a2, . . . ) and B = (b1, b2, . . . )andGet a result (e.g., “The median of A is bigger than the median of B”)together with an error probability p that the conclusion is wrong.If p is less than a significance level (upper bound) α, we can acceptthe conclusion.Otherwise, the observation is not significant.