[FEATURE REQUEST] Diversity Optimization

[btjanaka]

Description

Issue to track progress of diversity optimization implementation in pyribs.

General:

• Modify the scheduler API to support diversity optimization -> Support diversity optimization in Scheduler.tell #473
• Add tutorial
• Show how to plot landscapes (unsure if should make a viz function for this)

          fig, ax = plt.subplots(subplot_kw={"projection": "3d"})
          bound = config["dim"] / 2 * 5.12
          x = np.linspace(-bound, bound, 40)
          y = np.linspace(-bound, bound, 40)
          xxs, yys = np.meshgrid(x, y)
          measures = np.stack((xxs.ravel(), yys.ravel()), axis=1)
          novelty = scheduler.archive.compute_novelty(measures).reshape(
              xxs.shape)
          ax.plot_surface(xxs, yys, novelty, antialiased=False)
          plt.savefig(outdir / f"{name}_novelty_{itr:05d}.png")
          plt.close(fig)

Emitters:

• Modify all emitters to support diversity optimization (i.e., objective should be allowed to be None)
  • All but GradientArborescenceEmitter will work. Getting GradientArborescenceEmitter to work may not be straightforward.
• Add a NoveltyRanker -> Add NoveltyRanker for novelty search #477
• Add an NSLC Ranker

Novelty Search:

• Add ProximityArchive -> Add ProximityArchive for novelty search #472, Support unstructured archives [FEATURE REQUEST] #468
• Add visualization tool -> Add proximity_archive_plot for visualizing ProximityArchive #476
• Add novelty search to sphere.py -> Add novelty search with CMA-ES to sphere example #478
• Add local competition to ProximityArchive -> Support novelty search with local competition in ProximityArchive #481
  • Requires considering nearest neighbor behavior -> if solution is below threshold, compare it to nearest neighbor and replace the nearest neighbor if it has a better objective
  • Can be turned on with a local_competition flag
  • Objective should be required to be passed in when using local competition behavior
• Add threshold reduction to ProximityArchive
  • Something that makes sense is to add a coefficient, and every time the archive does not add enough solutions for X iterations, we can reduce the threshold by that coefficient. This way, solutions continue to be added to the archive.

DDS:

• Add ranker -> Add DensityRanker for density descent search #483
• Add archive
• Add visualization tool
• Add DDS to sphere.py

[gresavage]

@btjanaka FYI I'm working on the Novelty and NSLC rankers right now.

[btjanaka]

Sounds good; let's put those in a separate PR. By the way, would you like to meet sometime? Perhaps we can chat a bit about pyribs and these things especially since we've greatly expanded the scope beyond your original request. You can reach out to me on the pyribs Discord (https://discord.gg/QxhcJSqZ8G -- I'm username btjanaka) or over email (tjanaka@usc.edu)

[btjanaka]

@gresavage I talked with Matt Fontaine in our lab, and we agree your original approach to local competition makes sense. It just seems strange that there is no documentation of it in the NSLC paper. Roughly, if a solution is below the novelty threshold, we should compare its objective to its nearest neighbor and replace if necessary. I'll work on putting that back in.