tree_min_ui.pro

该程序是基于IDL平台下开法的应用随机搜索树进行搜索的优化算法实例！

;+
; NAME:
;
;  TREE_MIN_UI
;
; PURPOSE:
;
;  Uses a directed stochastic tree search for
;  a minimum of a function of a single variable.
;  This is a prototype global minimization search
;  strategy adapted from an algorithm discussed on
;  the following URL:
;
;  http://www.wfu.edu/~tacketst/epr.html
;
;  Credit for the underlying logic goes to Alan Tackett,
;  Forrest Charnock, Howard Shields, and Rick Matthews
;  at Wake Forest...all mistakes in this IDL implementation
;  are strictly mine!
;
;  This application allows the user to see how the
;  tree search progresses over each iteration.  Moreover
;  the user can specify their own function to minimize
;  and range over which to minimize the function.
;
; UI PARAMETERS:
;
;  Parameter range:
;     Comma-separated pair of numbers that
;     define the range over which the function
;     is defined (or to be searched).
;
;  # iterations:
;     Number of iterations for which the algorithm
;     is to search for the global minimum.
;
;  Branch probability decay width:
;     Standard deviation for probability to decay away on
;     a branch.  This decay width is in units of number of
;     visits to the node.  Small values (0,1 or 2) yield
;     searches that probe a lot of parameter space but not
;     in much depth.  Larger values yield searches that
;     are narrow in scope and are prone to getting stuck in
;     local minima.
;
;  Branch probability increment:
;     Amount by which to increment the branch upon
;     creating a new *best* node.  When this quantity is
;     large (e.g. 50) and the branch probability decay
;     width is large, then the search will be focused and
;     could get stuck in a local minimum.
;
;  Update time:
;     Elapsed time (in seconds...which depends on how fast
;     your computer is) between updating the display to show
;     how the tree evolves over time.
;
;  Minimize:
;     Pressing the button causes the program to begin minimizing
;     the function.
;
; AUTHOR:
;
;  Robert Dimeo
;  NIST Center for Neutron Research
;  National Institute of Standards and Technology
;  100 Bureau Drive-Stop 8562
;  Gaithersburg, MD 20899
;
; CATEGORY:
;
;  WIDGETS, OPTIMIZATION
;
; CALLING SEQUENCE:
;
;  IDL> TREE_MIN_UI
;
; REQUIREMENTS:
;
;  IDL 6.0 and higher.  The use of EXECUTE requires a full
;  IDL license to run the program so that the user can modify
;  the function to be minimized.
;
; REQUIRED PROGRAMS:
;
;  RMD_NODE__DEFINE
;
; COMMON BLOCKS:
;
;  NONE
;
; MODIFICATION HISTORY:
;
;  RMD -- Wrote 10/24/04
;  RMD -- Modified window updates while the iterations are in
;           progress so that the probability decay can be
;           viewed in real-time.
;
;-
; ************************************ ;
function rmd_node_func,p,_Extra = extra
compile_opt hidden,idl2
!except = 0
x = p
ret = execute(extra.equation,1)
return,y
end
; *********************************** ;
pro tree_min_ui_cleanup,tlb
compile_opt hidden,idl2
widget_control,tlb,get_uvalue = pstate
wdelete,(*pstate).winpix
obj_destroy,[(*pstate).ostart,(*pstate).obest]
heap_free,pstate
end
; *********************************** ;
pro tree_min_gen_fun,event
compile_opt hidden,idl2
widget_control,event.top,get_uvalue = pstate
if obj_valid((*pstate).ostart) then obj_destroy,(*pstate).ostart
prange_id = widget_info(event.top,find_by_uname = 'PRANGE')
widget_control,prange_id,get_value = txt
; Extract the lower and uppper limits separated by a comma
txt = txt[0]
txt_array = strsplit(txt,',',/extract)
prange = [float(txt_array[0]),float(txt_array[1])]

func = 'RMD_NODE_FUNC'
; Plot the function on a sensible range if autoscaled
nx = 1500 & xlo = prange[0] & xhi = prange[1]
dx = (xhi-xlo)/(nx-1.0) & x = xlo+dx*findgen(nx)
eq_choice = widget_info(event.top,find_by_uname = 'EQ_CHOICE')
equation = widget_info(eq_choice,/combobox_gettext)
ok = execute(equation,1)
if ~ok then return
*(*pstate).pdata = [[x],[y]]
end
; *********************************** ;
function tree_min_draw_tree,event,ocurrent
compile_opt hidden,idl2
; This is a recursive function that draws the
; entire tree structure in the current plot
; window.
widget_control,event.top,get_uvalue = pstate
yrange = (*pstate).autoyrange
current_yrange = (*pstate).yrange
ymin = yrange[0] < current_yrange[0]
ymax = yrange[1] > current_yrange[1]

if n_params() ne 2 then return,0
yi = yrange[1] & yf = yrange[0]+0.5*(yrange[1]-yrange[0])
nlevels = 15
dyy = (yf - yi)/(nlevels-1.)
nyy = 500
yy = yi+dyy*findgen(nyy)

if ~obj_valid(ocurrent) then return,0
ocurrent->get_property, parms = parms,level = level,     $
                        parent_node = parent,            $
                        branch_value = branch_value,     $
                        increment_value = increment_value

if obj_valid(parent) then begin
   parent->get_property,parms = parent_parms
   ; Draw the line of the appropriate thickness between
   ; self and parent
   xo = parms & xf = parent_parms
   if level ge nyy then return,0
   yo = yy[level] & yf = yy[level-1]
   plots,[xo,xf],[yo,yf],/data,color = (*pstate).yellow, $
      thick = 1+(float(branch_value)/increment_value)
endif

nchildren = ocurrent->count()
if nchildren eq 0 then return,0
child = ocurrent->get(/all)
for i = 0,nchildren-1 do begin
   result = tree_min_draw_tree(event,child[i])
   if obj_valid(result) then return,result
endfor
return,0
end
; *********************************** ;
pro tree_min_plot_fun,event,iter = iter
compile_opt hidden,idl2
widget_control,event.top,get_uvalue = pstate
x = (*(*pstate).pdata)[*,0]
y = (*(*pstate).pdata)[*,1]
; Make the y-range suitable for plotting the trees at the top of it.
if (*pstate).autoscale then begin
   ymin = min(y,max = ymax)
   dely = ymax-ymin
   (*pstate).yrange = [ymin-0.1*dely,ymax+dely]
   (*pstate).autoyrange = (*pstate).yrange
   xmin = min(x,max = xmax)
   delx = xmax-xmin
   (*pstate).xrange = [xmin-0.1*delx,xmax+0.1*delx]
endif
if n_elements(iter) gt 0 then $
   title = strtrim(string(iter+1),2) else $
   title = ''
plot,x,y,psym = 0,yrange = (*pstate).yrange,/ysty,          $
   background = (*pstate).black, color = (*pstate).white,   $
   xrange = (*pstate).xrange,/xsty, xtitle = '!3x', $
   ytitle = 'y',title = title

if obj_valid((*pstate).ostart) then $
   ret = tree_min_draw_tree(event,(*pstate).ostart)
if obj_valid((*pstate).obest) then begin
   (*pstate).obest->get_property,parms = parms,node_value = node_value,func = func

   eq_choice = widget_info(event.top,find_by_uname = 'EQ_CHOICE')
   equation = widget_info(eq_choice,/combobox_gettext)
   ybest = call_function(func,parms[0],_Extra = {equation:equation})
   out_coords = convert_coord(parms[0],ybest,/data,/to_normal)
   plots,[parms[0]],[ybest],psym = 8, $
      color = (*pstate).red
   xyouts,out_coords[0]+0.025,out_coords[1]-0.025,/normal,'!3Best min',   $
      charthick = 1.5,charsize = 1.5,color = (*pstate).red
endif
end
; *********************************** ;
pro tree_min_plot_refresh,event,iter = iter
compile_opt hidden,idl2
widget_control,event.top,get_uvalue = pstate
wset,(*pstate).winpix
if n_elements(iter) gt 0 then             $
   tree_min_plot_fun,event,iter = iter    $
else                                      $
   tree_min_plot_fun,event
wset,(*pstate).winvis
device,copy = [0,0,!d.x_size,!d.y_size,0,0,(*pstate).winpix]
end
; *********************************** ;
pro tree_min_calc,event
compile_opt hidden,idl2
widget_control,event.top,get_uvalue = pstate
iter_id = widget_info(event.top,find_by_uname = 'ITERATIONS')
widget_control,iter_id,get_value = iter & itmax = long(iter[0])
decay_id = widget_info(event.top,find_by_uname = 'DECAY_WIDTH')
widget_control,decay_id,get_value = decay & decay = float(decay[0])
incr_id = widget_info(event.top,find_by_uname = 'INCREMENT')
widget_control,incr_id,get_value = increment & increment = long(increment[0])
delay_id = widget_info(event.top,find_by_uname = 'UPDATE')
widget_control,delay_id,get_value = delay & delay = float(delay[0])
prange_id = widget_info(event.top,find_by_uname = 'PRANGE')
widget_control,prange_id,get_value = txt
; Extract the lower and uppper limits separated by a comma
txt = txt[0]
txt_array = strsplit(txt,',',/extract)
prange = [float(txt_array[0]),float(txt_array[1])]

eq_choice = widget_info(event.top,find_by_uname = 'EQ_CHOICE')
equation = widget_info(eq_choice,/combobox_gettext)

func = 'RMD_NODE_FUNC'
delay_time = delay
vis_plot = 1B
id = '0-0'
(*pstate).autoscale = 1B
increment_value = increment
decay_width = decay

if obj_valid((*pstate).ostart) then obj_destroy,(*pstate).ostart
ostart = obj_new('rmd_node',id,  prange = prange,                    $
                                 increment_value = increment_value,  $
                                 decay_width = decay_width,          $
                                 func = func,                        $
                                 _Extra = {equation:equation},       $
                                 level = 0                           )
(*pstate).ostart = ostart

; Plot the function on a sensible range
nx = 1500 & xlo = prange[0] & xhi = prange[1]
dx = (xhi-xlo)/(nx-1.0) & x = xlo+dx*findgen(nx)
y = call_function(func,x,_Extra = {equation:equation})
; Make the y-range suitable for plotting the trees at the top of it.
ymin = min(y,max = ymax)
dely = ymax-ymin
yrange = [ymin-0.1*dely,ymax+dely]
tree_min_plot_refresh,event
yi = yrange[1] & yf = yrange[0]+0.5*(yrange[1]-yrange[0])
nlevels = 15
dyy = (yf - yi)/(nlevels-1.)
nyy = 200
yy = yi+dyy*findgen(nyy)