php/Math   
Recreational Mathematics   
   home  |  library  |  contact
 Math Notes
 Math Programming [25]
 Regression [3]
 Data Mining [17]
 Notation [6]
 Linear Algebra [9]
 Stats & Prob [15]
 Math Cognition [5]
 Space & Physics [6]
 Formulas [5]
 Fun & Games [2]
 Haskell [1]
 Bayes Theory [1]
 Site News [0]
 Math Projects [5]
 Polynomials [1]
 Calculus [9]
 Number Theory [3]
 Optimization [2]
 Financial [1]

 Math Links
 PHP/ir
 Andrew Gelman
 Chance Wiki
 Daniel Lemire
 KD Knuggets
 Social Stats
 MySQL Performance
 Hunch.net
 Matthew Hurst
 JMLR
 JSS
 Hal Daume III
 Math Notes >> Optimization

Particle Swarm Optimization (PSO) : Part 1 [Optimization
Posted on May 26, 2008 @ 02:47:13 PM by Paul Meagher

An interesting area of research that I was not very familiar with is Computational Swarm Intelligence. A book by A.P. Engelbrecht (2005), "Fundamentals of Computational Swarm Intelligence", John Wiley & Sons, offers an excellent overview of the area. Andries breaks the field down into three main subfields:

  1. Genetic Algorithm Research
  2. Particle Swarm Optimization
  3. Ant Colony Optimization

The book takes an "engineering approach" to the topic areas: The computational tools used to study these areas can be applied to a host of engineering problems requiring optimization.

The book is 599 pages long. The section on Particle Swarm Optimization is around 275 pages long. It is a book within the book and probably the best coverage of this topic area if you have a specific interest in Particle Swarm Optimization PSO algorithms.

The section of the book on PSO presents this as the first formula to learn:

xi(t) = xi(t) + vi(t + 1)

This tells us that the position of particle i in a multidimensional space is a function of the position of the particle at time xi(t) and the velocity of the particle vi(t + 1).

You can use a uniform random number generator to initialize the positions of the particles.

xi(0) ~ U(xmin, xmax)

Permalink 

Longest Common Subsequence [Optimization
Posted on February 21, 2008 @ 10:13:09 PM by Paul Meagher

The Longest Common Subsequence algorithm compares two strings and finds the longest subsequence shared by both strings. There are lots of applications, however, two are particularly noteworthy:

  1. Computing the similarity between sequences of genetic material.
  2. Computing differences between files (i.e., unix "diff" command).

So, without further ado, here is an algorithm for computing the Longest Common Subsequence:

<?php
/**
* Port of Sedgewick & Wayne's Longest Common Subsequence algorithm 
* found here:
*
* @see http://www.cs.princeton.edu/introcs/96optimization/LCS.java.html
* @see http://www.cs.princeton.edu/introcs/96optimization/
*
* @author Paul Meagher
* @ported Feb 21, 2008
*
* See also:
*
* @see http://www.ics.uci.edu/~eppstein/161/960229.html
*
* @param string $S1 first string 
* @param string $S2 second string 
* @returns string containing common subsequence or empty string
*/
function string_lcs($S1$S2) {

  
$m strlen($S1);
  
$n strlen($S2);

  
// A[i][j] = length of LCS of S1[i..m] and S2[j..n]
  
$A = array();

  
// compute length of LCS and all subproblems via dynamic programming
  
for ($i $m-1$i >= 0$i--) {
    for (
$j $n-1$j >= 0$j--) {
      if (
$S1[$i] == $S2[$j])
        
$A[$i][$j] = $A[$i+1][$j+1] + 1;
      else 
        
$A[$i][$j] = max($A[$i+1][$j], $A[$i][$j+1]);
    }
  }

  
// recover LCS itself and print it to standard output
  
$i 0;
  
$j 0;
  
$LCS "";
  while(
$i $m && $j $n) {
    if (
$S1[$i] == $S2[$j]) {
      
$LCS .= $S1[$i];
      
$i++;
      
$j++;
    } elseif (
$A[$i+1][$j] >= $A[$i][$j+1]) 
      
$i++;
    else                                 
      
$j++;
  }
  
  return 
$LCS;

}
  
?>  

Here is a test program with the output displayed in the source code:

<?php

include "string_lcs.php";

$S1 "abcdefghijk";
$S2 "ijklmnop";

$subsequence string_lcs($S1$S2);
echo 
$subsequence;

// Output: ijk

?>

I've taken a few liberties in my port of Sedgewick and Wayne's LCS class. I reimplemented the LCS class as a string_lcs function as a class seemed like overkill at this point. I also use the word "string_" as a prefix for the function name. I used this prefix in anticipation of eventually building a library of such string functions (in addition to PHP's collection of string functions). I also renamed some variables to be more mnemonic (e.g., $S1, $S2) or standard (e.g., $A, $m, $n) and changed the capitalization of variable names to conform with whether they are being treated as a scalar (lowercase) or vector/matrix quantity (uppercase).

Consult some of the links contained in the source to learn more about how the algorithm works and about Dynamic Programming more generally.

Permalink 

 Archive 
 


php/Math Project
© 2011. All rights reserved.