[Help] Goal seek macro

Need help, or want to share a macro? Post here!
edwilliams16
Veteran
Posts: 1200
Joined: Thu Sep 24, 2020 10:31 pm
Location: Hawaii
Contact:

Re: [Help] Goal seek macro

Post by edwilliams16 »

@openbrain If you want to tweak this further, once you have found brackets for the root, you can use Brent's method to find it. https://en.wikipedia.org/wiki/Brent%27s_method It combines the certainty of finding the root you get with bisection with the faster convergence of the secant method. The weakness of the faster converging secant method (which is a essentially Newton's method using a numerical derivative) is that the iterates can wander outside the bracket - Brent fixes this. It's a favorite.

However, in a simple problem like how does volume change with some dimension (where the function is monotonic and there is guaranteed to be only one root), just about any method will work - but some require more iterations than others.
openBrain
Veteran
Posts: 7882
Joined: Fri Nov 09, 2018 5:38 pm

Re: [Help] Goal seek macro

Post by openBrain »

edwilliams16 wrote: Sun Jan 24, 2021 9:28 pm @openbrain If you want to tweak this further, once you have found brackets for the root, you can use Brent's method to find it.
Not that I'm not interested in, but my spare time is limited and scipy is capable. :) Will put effort in something else. ;)
suzanne.soy
Posts: 52
Joined: Sat Dec 19, 2020 11:55 pm

Re: [Help] Goal seek macro

Post by suzanne.soy »

Chiming in because this is something I've tried (and failed) a couple of weeks ago :)

I had tried to make a similar optimization macro, my goal was to tweak multiple parameters so that some 2D shapes fill a rectangle without overlapping, optimizing e.g. for the scale of the shapes.

I used an App::FeaturePython object, which describes some tweakable parameters with their ranges, the first parameter is the goal (to minimize or maximize), and the Mapping field tells it how to assign tweakable parameters to the position, rotation, scale of the objects. This allows to bind the same scale to two objects. In retrospect, I should have used simple properties, and used expressions in the objects-to-be-moved to copy these properties.

My approach was to use a genetic algorithm. This was probably not the best idea, as combining the rotation of one solution with the position of another is unlikely to give a valid result, when the rectangle is getting cramped.

Another problem is that I didn't implement a good fitness function for the tweakable parameters, so the algorithm is just groping in the dark really.

So the code below requires a valid starting position otherwise it takes forever to find one, and even with that it converges at a horrendously slow speed. Please file this in the "failed experiments" folder :lol:

I'll probably revive this in the future and use some insights from this thread (use Scipy, make sure the fitness function has a smooth gradient close to the optimum), and give the algorithm a hand:
* instead of fitting in a fixed rectangle, it makes sense rotate the group of shapes as a whole a few times until its bounding box is the smallest, and use that as a metric
* instead of maximizing the scale (which adds an extra parameter) I should minimize the delta between the best bounding box's aspect ratio and the target aspect ratio; it's easy to scale to get the desired size once the aspect ratio is optimal
* minimize the number of parameters: since the bounding box should be measured, the absolute position doesn't matter, only the relative positions of the objects, so one object can be fixed in (0,0), the same applies to the rotation.
* rotate objects around their centre of mass instead of rotating around an arbitrary object origin
* try to find a way to "fix" an invalid solution instead of discarding it (e.g. if the shapes intersect, shift one until they don't anymore)

Surely these problem-specific tricks can be generalized to have decent guidelines for an optimization problem, I'll have to think about this.

Code: Select all

# TODO:
# fitness: distance to other shapes
# compute rotated bounding box witù minimum area and rotate the page to fit (+portrait or landscape)

from functools import cmp_to_key
import random

def applyConfiguration(configuration, mapping, objects):
  for i,o in enumerate(objects):
    x,y,angle,scale = mapping[i]
    o.Placement.Base.x = configuration[x][1]
    o.Placement.Base.y = configuration[y][1]
    o.Placement.Rotation.Angle = configuration[angle][1]
    o.Scale = configuration[scale][1]

def isValid(page, configuration, mapping, objects):
  applyConfiguration(configuration, mapping, objects)
  for object in objects:
    if object.Shape.cut(page.Shape).Area > 0:
      return False
    for other in objects:
      if object != other and object.Shape.common(other.Shape).Area > 0:
        return False
  return True

def compare(configuration1, configuration2, tolerance):
  if configuration2 is None:
    return True
  if configuration1 is None:
    return False
  """True if configuration1 is better than configuration2. This is not a proper rder because of the tolerance"""
  for ((name, vx, min, max, goal),(_, vy, _, _, _)) in zip(configuration1,configuration2):
    if goal == 'max':
      v1, v2 = vx, vy
    elif goal == 'min':
      v1, v2 = vy,vx
    elif goal == '':
      break # uncomparable
    else:
      raise ValueError("Optimize2D: Invalid goal:" + str(goal) + " in configuration " + str(configuration1) + ". Expected 'min' or 'max'.")
    if v1 > v2 + tolerance:
      return 1
    elif v1 < v2 - tolerance:
      return -1
    else:
      continue
  return 0

def evolve(configuration, best, population, generation, tolerance):
  configuration = list(configuration) # copy to prevent mutation
  r = random.random()
  if r < 0.05:
    # completely random starting point
    for i in range(len(configuration)):
      name, v, min, max, goal = configuration[i]
      v = random.uniform(min, max)
      configuration[i] = (name, v, min, max, goal)
  elif r < 0.3:
    # completely randomize a gene trying to improve the best case
    for attempt in range(50):
      i = random.randrange(len(configuration))
      name, v, min, max, goal = configuration[i]
      v = random.uniform(min, max)
      configuration[i] = (name, v, min, max, goal)
      if compare(configuration, best, tolerance)> 0:
        break
  elif r < 0.5:
    # slightly randomize all genes
    for i in range(len(configuration)):
      name, v, min, max, goal = configuration[i]
      delta = (max-min)*(1.0/(generation+1))
      v = v + random.uniform(-delta,delta) 
      if v < min: v = min
      if v > max: v = max
      configuration[i] = (name, v, min, max, goal)
  elif r < 0.7:
    # mix with other from population
    other = random.randrange(len(population))
    for i in range(len(configuration)):
      name, v1, min, max, goal = configuration[i]
      _, v2, _, _, _= population[other][i]
      if random.random() < 0.5:
        v = v1
      else:
        v = v2
      configuration[i] = (name, v, min, max, goal)
  else:
    # slightly randomize a gene
    i = random.randrange(len(configuration))
    name, v, min, max, goal = configuration[i]
    delta = (max-min)*(1.0/(generation+1))
    v = v + random.uniform(-delta,delta) 
    if v < min: v = min
    if v > max: v = max
    configuration[i] = (name, v, min, max, goal)
  return configuration

def auto(page, initialConfiguration, min, max, mapping, objects, tolerance, maxPopulation, promote, generations):
  #random.uniform(min, max)
  population = [initialConfiguration]
  prevbest = initialConfiguration
  best = initialConfiguration
  for generation in range(generations):
    prevbest = best
    best = population[0]
    print("score=" + str(best[0][1])+', pop=' + str(len(population)), ', better?' + str(compare(best, prevbest, tolerance)) + "prev=" + str(prevbest[0][1]))
    offsprings = [evolve(configuration, best, population, generation, tolerance) for configuration in population]
    offsprings = [configuration for configuration in offsprings if isValid(page, configuration, mapping, objects)]
    random.shuffle(population)
    population = population + offsprings + [initialConfiguration]
    population = sorted(population, reverse = True, key = cmp_to_key(lambda x,y: compare(x,y,tolerance)))
    population = population[:promote] + random.choices(population = population, k = maxPopulation-promote)
  return population[0]

def line(name, v, min, max, goal = ''):
  return (name, float(v), float(min), float(max), goal)

def main(o):
  configuration = [line(*l.strip().split()) for l in o.Configuration if l.strip()]
  mapping = [tuple(l.strip().split()) for l in o.Mapping if l.strip()]  
  page = o.Page
  objects = o.Objects
  tolerance = o.Tolerance
  maxPopulation = o.MaxPopulation
  promote = o.Promote
  generations = o.Generations

  configuration_indices = dict((name, i) for i, (name,_,_,_,_) in enumerate(configuration))
  mapping = [tuple(configuration_indices[ref] for ref in m) for m in  mapping]

  best = auto(page, configuration, min, max, mapping, objects, tolerance, maxPopulation, promote, generations)
  if best:
    applyConfiguration(best, mapping, objects)
    o.Configuration = [' '.join([str(x) for x in c]) for c in best]
  else:
    applyConfiguration(configuration, mapping, objects)
    raise ValueError("Couldn't find a suitable configuration (not a ValueError)")

def mk():
  o = App.ActiveDocument.addObject('App::FeaturePython', 'Optimize2D')
  o.addProperty("App::PropertyStringList", "Configuration")
  o.Configuration =  """scale 0.1 0.1 5 max
rot1 0 0 0
x1 120 0 300
y1 60 0 400
rot2 0 0 90
x2 90 0 300
y2 190 0 400""".split('\n')
  o.addProperty("App::PropertyStringList", "Mapping")
  o.Mapping = """x1 y1 rot1 scale
x2 y2 rot2 scale""".split('\n')
  o.addProperty("App::PropertyLinkList", "Objects")
  o.Objects = [App.ActiveDocument.Link, App.ActiveDocument.Link001]
  o.addProperty("App::PropertyFloat", "Tolerance")
  o.Tolerance = 0.00001
  o.addProperty("App::PropertyLink", "Page")
  o.Page = App.ActiveDocument.Binder
  o.addProperty("App::PropertyInteger", "MaxPopulation", "Genetic algorithm")
  o.MaxPopulation = 30
  o.addProperty("App::PropertyInteger", "Promote", "Genetic algorithm")
  o.Promote = 10
  o.addProperty("App::PropertyInteger", "Generations", "Genetic algorithm")
  o.Generations = 20

if not hasattr(App.ActiveDocument, 'Optimize2D'):
  mk()

main(App.ActiveDocument.Optimize2D)

Code: Select all

OS: Ubuntu 20.04.1 LTS (XFCE/xubuntu)
Word size of OS: 64-bit
Word size of FreeCAD: 64-bit
Version: 0.19.23756 (Git) AppImage
Build type: Release
Branch: master
Hash: 9c6e9184930a52b165a0b7274e3a45d1006bfe67
Python version: 3.8.6
Qt version: 5.12.5
Coin version: 4.0.0
OCC version: 7.4.0
Locale: English/United Kingdom (en_GB)
Attachments
screenshot-2D-pack.png
screenshot-2D-pack.png (135.3 KiB) Viewed 1194 times
autoscale_macro.FCStd
(292.81 KiB) Downloaded 38 times
:?: Please mark your posts as [solved] :!:
:idea: If the answer you got is a good fit for the wiki, you can edit it!
FreeCAD modelling & coding workbenches+macros: twitch GitHub
kisolre
Veteran
Posts: 4051
Joined: Wed Nov 21, 2018 1:13 pm

Re: [Help] Goal seek macro

Post by kisolre »

Could somebody advice why is this happening? I tried to start the macro with recent build and get this:

Code: Select all

22:11:23  Traceback (most recent call last):
  File "C:/Users/Wivern/AppData/Roaming/FreeCAD/Macro/_GoalSeek.FCMacro", line 18, in <module>
    from scipy.optimize import minimize
  File "E:\FC_DevVMBuild\bin\Lib\site-packages\shiboken2\files.dir\shibokensupport\__feature__.py", line 142, in _import
    return original_import(name, *args, **kwargs)
  File "E:\FC_DevVMBuild\bin\lib\site-packages\scipy\optimize\__init__.py", line 387, in <module>
    from .optimize import *
  File "E:\FC_DevVMBuild\bin\Lib\site-packages\shiboken2\files.dir\shibokensupport\__feature__.py", line 142, in _import
    return original_import(name, *args, **kwargs)
  File "E:\FC_DevVMBuild\bin\lib\site-packages\scipy\optimize\optimize.py", line 36, in <module>
    from ._numdiff import approx_derivative
  File "E:\FC_DevVMBuild\bin\Lib\site-packages\shiboken2\files.dir\shibokensupport\__feature__.py", line 142, in _import
    return original_import(name, *args, **kwargs)
  File "E:\FC_DevVMBuild\bin\lib\site-packages\scipy\optimize\_numdiff.py", line 6, in <module>
    from scipy.sparse.linalg import LinearOperator
  File "E:\FC_DevVMBuild\bin\Lib\site-packages\shiboken2\files.dir\shibokensupport\__feature__.py", line 142, in _import
    return original_import(name, *args, **kwargs)
  File "E:\FC_DevVMBuild\bin\lib\site-packages\scipy\sparse\__init__.py", line 227, in <module>
    from .base import *
  File "E:\FC_DevVMBuild\bin\Lib\site-packages\shiboken2\files.dir\shibokensupport\__feature__.py", line 142, in _import
    return original_import(name, *args, **kwargs)
  File "E:\FC_DevVMBuild\bin\lib\site-packages\scipy\sparse\base.py", line 4, in <module>
    from .sputils import (isdense, isscalarlike, isintlike,
  File "E:\FC_DevVMBuild\bin\Lib\site-packages\shiboken2\files.dir\shibokensupport\__feature__.py", line 142, in _import
    return original_import(name, *args, **kwargs)
  File "E:\FC_DevVMBuild\bin\lib\site-packages\scipy\sparse\sputils.py", line 8, in <module>
    from scipy._lib._util import prod
  File "E:\F<class 'SyntaxError'>: invalid syntax (process.py, line 262)
22:11:44  Save AutoRecovery file: Needed time: 0ms
Is this caused by some upgrade of SciPy or Shiboken?
This result is from this FreeCAD version (latest local build):
OS: Windows 8.1 Version 6.3 (Build 9600)
Word size of FreeCAD: 64-bit
Version: 0.20.25026 (Git)
Build type: Release
Branch: master
Hash: 85f37a1dbcb757efad32b7598ac0f99af021af8f
Python version: 3.8.6+
Qt version: 5.15.2
Coin version: 4.0.1
OCC version: 7.5.0
Locale: Bulgarian/Bulgaria (bg_BG)

the macro from my last post and the attached file as an example.
Attachments
GoalSeekTest002.FCStd
(581.28 KiB) Downloaded 28 times
User avatar
Chris_G
Veteran
Posts: 2102
Joined: Tue Dec 31, 2013 4:10 pm
Location: France
Contact:

Re: [Help] Goal seek macro

Post by Chris_G »

It works fine here :

Code: Select all

OS: Manjaro Linux (KDE/plasma)
Word size of FreeCAD: 64-bit
Version: 0.20.25001 (Git)
Build type: Release
Branch: master
Hash: ff26df0a6d21c6c6a397e5f11d7857d3f63841cc
Python version: 3.9.5
Qt version: 5.15.2
Coin version: 4.0.1
OCC version: 7.5.0
Locale: French/France (fr_FR)
Maybe your FC package doesn't include scipy anymore ?
Do you get an error when typing this in the python console ? :

Code: Select all

from scipy.optimize import minimize
kisolre
Veteran
Posts: 4051
Joined: Wed Nov 21, 2018 1:13 pm

Re: [Help] Goal seek macro

Post by kisolre »

Chris_G wrote: Mon Jun 07, 2021 8:46 pm Do you get an error when typing this in the python console ? :

Code: Select all

>>> from scipy.optimize import minimize
Traceback (most recent call last):
  File "<input>", line 1, in <module>
  File "E:\FC_DevVMBuild\bin\Lib\site-packages\shiboken2\files.dir\shibokensupport\__feature__.py", line 142, in _import
    return original_import(name, *args, **kwargs)
  File "E:\FC_DevVMBuild\bin\lib\site-packages\scipy\optimize\__init__.py", line 387, in <module>
    from .optimize import *
  File "E:\FC_DevVMBuild\bin\Lib\site-packages\shiboken2\files.dir\shibokensupport\__feature__.py", line 142, in _import
    return original_import(name, *args, **kwargs)
  File "E:\FC_DevVMBuild\bin\lib\site-packages\scipy\optimize\optimize.py", line 36, in <module>
    from ._numdiff import approx_derivative
  File "E:\FC_DevVMBuild\bin\Lib\site-packages\shiboken2\files.dir\shibokensupport\__feature__.py", line 142, in _import
    return original_import(name, *args, **kwargs)
  File "E:\FC_DevVMBuild\bin\lib\site-packages\scipy\optimize\_numdiff.py", line 6, in <module>
    from scipy.sparse.linalg import LinearOperator
  File "E:\FC_DevVMBuild\bin\Lib\site-packages\shiboken2\files.dir\shibokensupport\__feature__.py", line 142, in _import
    return original_import(name, *args, **kwargs)
  File "E:\FC_DevVMBuild\bin\lib\site-packages\scipy\sparse\__init__.py", line 227, in <module>
    from .base import *
  File "E:\FC_DevVMBuild\bin\Lib\site-packages\shiboken2\files.dir\shibokensupport\__feature__.py", line 142, in _import
    return original_import(name, *args, **kwargs)
  File "E:\FC_DevVMBuild\bin\lib\site-packages\scipy\sparse\base.py", line 4, in <module>
    from .sputils import (isdense, isscalarlike, isintlike,
  File "E:\FC_DevVMBuild\bin\Lib\site-packages\shiboken2\files.dir\shibokensupport\__feature__.py", line 142, in _import
    return original_import(name, *args, **kwargs)
  File "E:\FC_DevVMBuild\bin\lib\site-packages\scipy\sparse\sputils.py", line 8, in <module>
    from scipy._lib._util import prod
  File "E:\FC_DevVMBuild\bin\Lib\site-packages\shiboken2\files.dir\shibokensupport\__feature__.py", line 142, in _import
    return original_import(name, *args, **kwargs)
  File "E:\FC_DevVMBuild\bin\lib\site-packages\scipy\_lib\_util.py", line 7, in <module>
    from multiprocessing import Pool
  File "E:\FC_DevVMBuild\bin\Lib\site-packages\shiboken2\files.dir\shibokensupport\__feature__.py", line 142, in _import
    return original_import(name, *args, **kwargs)
  File "C:\Users\Wivern\AppData\Roaming\FreeCAD\Mod\retr3d\multiprocessing\__init__.py", line 64, in <module>
    from multiprocessing.process import Process, current_process, active_children
  File "E:\FC_DevVMBuild\bin\Lib\site-packages\shiboken2\files.dir\shibokensupport\__feature__.py", line 142, in _import
    return original_import(name, *args, **kwargs)
  File "C:\Users\Wivern\AppData\Roaming\FreeCAD\Mod\retr3d\multiprocessing\process.py", line 262
    except SystemExit, e:
                     ^
SyntaxError: invalid syntax
>>> 
edwilliams16
Veteran
Posts: 1200
Joined: Thu Sep 24, 2020 10:31 pm
Location: Hawaii
Contact:

Re: [Help] Goal seek macro

Post by edwilliams16 »

Code: Select all

File "C:\Users\Wivern\AppData\Roaming\FreeCAD\Mod\retr3d\multiprocessing\process.py", line 262
    except SystemExit, e:
                     ^
SyntaxError: invalid syntax
Says there is a syntax error in your retr3d workbench.
kisolre
Veteran
Posts: 4051
Joined: Wed Nov 21, 2018 1:13 pm

Re: [Help] Goal seek macro

Post by kisolre »

edwilliams16 wrote: Mon Jun 07, 2021 10:20 pm Says there is a syntax error in your retr3d workbench.
Good catch. I removed retr3d WB, restarted FreeCAD and now the import works ok and the macro also works.
But why should (unmantained? and probably broken) another workbench mess with the work of an unrelated macro? Is it possible that there is some deeper problem that just gets exposed with the combination of mods i have here?
timo.kinnunen
Posts: 3
Joined: Wed May 11, 2022 8:22 pm

Re: [Help] Goal seek macro

Post by timo.kinnunen »

kisolre wrote: Tue Jun 08, 2021 5:32 am But why should (unmantained? and probably broken) another workbench mess with the work of an unrelated macro? Is it possible that there is some deeper problem that just gets exposed with the combination of mods i have here?
retr3d contains its own copy of the multiprocessing module, but this copy is for Python 2 and uses syntax that's not valid in Python 3. This explains the what part of the error.

As to why this happens, in Retr3d/utilityFunctions.py there's this weird piece of code:

import sys
sys.path.append(os.path.dirname(os.path.abspath(__file__)))
import logging
sys.path.append(os.path.dirname(os.path.abspath(__file__)))


This adds the directory containing retr3d to the module loading path which I'm guessing, when combined with customized module loading used in FreeCAD, allows the copy to be found and imported over the one from the python distribution.

As to should this happen, I'm unsure. The Python documentation for sys.path offers little guidance, simply saying: "A program is free to modify this list for its own purposes." So this could be a bug, but it being a feature wouldn't surprise me either.
User avatar
onekk
Veteran
Posts: 2445
Joined: Sat Jan 17, 2015 7:48 am
Contact:

Re: [Help] Goal seek macro

Post by onekk »

probably with a method of same name it utilize the "last" found in sys.path.

As in pythin you could "rewrite" methods this is a "feature", once you know the mechanics.

Sometimes it will became a "problem", probably some "warning" that coulb be activated in python interpreter about "redefining functions" will be s good way.

or simply the import statement is importing using

Code: Select all

from something import *


that is considered "bad practice" most of the times.

Regards

Carlo D.
My English and Italian Scripting Guide https://github.com/onekk/freecad-doc.
My Blog: https://onekk-maker.blogspot.com/

To help development see on GitHub Page

For enquiry about customized FC Scripting job PM me.
Post Reply