[GAP Forum] Local search?

[Steve Linton]

Dear GAP Forum,

On Sun, 23 Jan 2005 09:16:21 +0100
wh at icparc.ic.ac.uk wrote:

> Dear GAP Forum,
> 
> Are any of you aware of any software (GAP or otherwise) or literature
> regarding using local search to find a group element with certain properties?
> I am interested in using such techniques, so any such software or literature
> would be useful to me.
> 
> By local search I mean techniques along the lines of starting with a
> more-or-less random element that does not have the desired properties,
> moving to a "nearby"/similar element that might be closer to having the
> desired properties, and repeating until one either finds an element that
> meets the requirements or gives up.  (Examples of such techniques include
> hill climbing, tabu search, greedy randomised adaptive search procedures
> (GRASPs), and possibly simulated annealing and genetic algorithms.)
> 
> Basically, I want to do a relatively quick check to see whether I can find
> such an element, but I don't care too much if I fail to find one, even if
> one exists.
> 

The only work anyone has been able to think of in this direction is some work
by the Magnus group in New York on using genetic algorithms to do computations
with finitely-presented groups. 

A. D. Miasnikov\ and\ A. G. Myasnikov, in {\it Computational and experimental
group theory}, 89--114, Contemp. Math., 349, Amer. Math. Soc., Providence, RI,
2004; MR2077761

A. D. Miasnikov, Internat. J. Algebra Comput. {\bf 9} (1999), no.~6, 671--686;
MR1727164 (2001k:20067) 

I have been involved in some discussions of this idea with Warwick on another
mailing list. For the interest if the forum, and in case anyone else can
contribute, we're interested in methods that attempt to solve problems in
permutation groups that would normally require a backtrack search, such as "is
there a g \in G which maps a set S of points into another set T (possibly
larger)". We're interested in methods that have a reasonable chance of
returning a positive solution quickly, if there is one, but we can tolerate
some chance of error.

	Steve Linton
-- 
Steve Linton	School of Computer Science  &
      Centre for Interdisciplinary Research in Computational Algebra
	     University of St Andrews 	 Tel   +44 (1334) 463269
http://www.dcs.st-and.ac.uk/~sal	 Fax   +44 (1334) 463278