SEMINAR - Dr. Peter Sadler
The Department Welcomes Dr. Peter Sadler. Peter is a visiting us from the Earth Sciences Department at the University of California Riverside.
His research instrests include; Quantitative biostratigraphy, rates and scaling laws of geologic processes; completeness of the stratigraphic record; synorogenic sedimentation.
Peters recent projects include; CONOP software for stratigraphic correlation and seriation; Ordovician and Silurian time scales; graptolite and conodont species richness and longevity; scaling laws for progradation, aggradation, and volumes of siliciclastic passive margins; CHRONOS and EARTHTIME geoinformatics initiatives; modeling fire mosaics and vegetation conversion.
Peter will lecture on the "High-resolution Geologic Time Scales and Biodiversity Curves: a Traveling Salesman Problem"; Wednesday the 31st of January.
4 comments:
Here is a abstract submitted by Peter for the 2003 AAPG Annual Meeting, it nicely explains the Traveling Salesman Problem
***********************************
Stratigraphic Correlation and Seriation as a Traveling Salesman Problem
Peter M. Sadler, Department of Earth Sciences, University of California Riverside, University of California, Riverside, CA 92521, phone: 909 787 5616, fax: 909 787 4324, peter.sadler@ucr.edu
In traveling salesman problems (TSPs), a set of cities must be visited in the order that incurs the lowest travel cost. The time required to evaluate all possible routes increases so rapidly with the number of cities that exhaustive search for the best route becomes impossible. Operations research has developed heuristic non-exhaustive search strategies that solve large instances of TSPs, e.g. simulated annealing, genetic algorithms, and tabu-search. Stratigraphic seriation and correlation are tasks analogous to TSPs and solvable by the same methods. The cities in the TSP become event horizons, e.g. appearances and disappearances of fossil taxa, paleomagnetic reversals, and ash beds. The possible routes connecting the cities become hypothetical historical sequences of stratigraphic events. Typically, no sequence can match every local stratigraphic section because the order of observed range ends for fossil taxa varies from section to section. Thus, each hypothetical sequence incurs a cost which is the net mismatch, summed across all events and sections. The solution is the sequence with the lowest mismatch and may vary with the measure of mismatch - net range extension, pair-wise event reversals, implied but unobserved coexistences, etc. The solution time increases with the number of sections and the number of events. Correlation problems involving over 2700 range-end events and 230 sections have been solved in this fashion on desktop computers. The results are time scales with up to an order of magnitude more resolving power than traditional biozones and biodiversity curves for which taxa are not binned into coarse time intervals.
CONOP Download Page
This program was developed by Peter M. Sadler
CONSTRAINED OPTIMIZATION APPROACHES TO THE PALEOBIOLOGIC CORRELATION AND SERIATION PROBLEMS:
The CONOP program minimizes the simplifying assumptions and maximizes the flexibility of the choice of measures of fit between solutions and the data. This is achieved by inverting the solution process. Instead of building a solution from the data, CONOP works through a series of iteratively improved guesses about the solution. Each guess is compared with the data; the misfit between the solution and data guides the next guess. Geophysicists like to call the process “inversion.” Others may notice elements of Bayesian logic -- modify prior notions about the
solution by reference to the data.
Teaching Large Classes: Dr. Peter Sadler, Department of Earth Sciences
Real Player needed: Download the free player for Windows / Mac
Challenging Students to Learn in the Large Class Environment (1:20)
Difficulties with Testing in Large Classes (1:48)
Here is a web site at Georgia Tech devoted to the history of TSP computation and to on-going research towards the solution of large-scale examples of the TSP
The Traveling Salesman Problem
The simplicity of the statement of the traveling salesman problem is deceptive -- the TSP is one of the most intensely studied problems in computational mathematics and yet no effective solution method is known for the general case. Indeed, the resolution of the TSP would settle the P versus NP problem and fetch a $1,000,000 prize from the Clay Mathematics Institute.
Post a Comment