{"action":"created","issue":{"url":"https://api.github.com/repos/jMetal/jMetal/issues/26","labels_url":"https://api.github.com/repos/jMetal/jMetal/issues/26/labels{/name}","comments_url":"https://api.github.com/repos/jMetal/jMetal/issues/26/comments","events_url":"https://api.github.com/repos/jMetal/jMetal/issues/26/events","html_url":"https://github.com/jMetal/jMetal/issues/26","id":45169952,"number":26,"title":"Algorithm measurements","user":{"login":"matthieu-vergne","id":1774210,"avatar_url":"https://avatars.githubusercontent.com/u/1774210?v=3","gravatar_id":"","url":"https://api.github.com/users/matthieu-vergne","html_url":"https://github.com/matthieu-vergne","followers_url":"https://api.github.com/users/matthieu-vergne/followers","following_url":"https://api.github.com/users/matthieu-vergne/following{/other_user}","gists_url":"https://api.github.com/users/matthieu-vergne/gists{/gist_id}","starred_url":"https://api.github.com/users/matthieu-vergne/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/matthieu-vergne/subscriptions","organizations_url":"https://api.github.com/users/matthieu-vergne/orgs","repos_url":"https://api.github.com/users/matthieu-vergne/repos","events_url":"https://api.github.com/users/matthieu-vergne/events{/privacy}","received_events_url":"https://api.github.com/users/matthieu-vergne/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":33,"created_at":"2014-10-07T21:17:28Z","updated_at":"2015-03-06T21:48:39Z","closed_at":null,"body":"Considering that you are revising the conceptual modeling of your framework, I come here with an idea about how to model measurements that you could exploit in an experiment or simply as a way to get on the fly measures of algorithms (without being forced to use any experimental environment).\r\n\r\n# Measures: Pull VS Push\r\n\r\nFirst of all, measure makes no sense out of a specific algorithm. Speaking for instance about population size in an algorithm which does not manage a population of individuals makes no sense. Thus, I would delegate the definition of the measures to the specific algorithms. Consequently, when I speak about a measure I take the perspective of the algorithm being measured. From this perspective, I see two kinds of measures:\r\n- *pull* measures, which come when requested by external entities (e.g. what is the current population size?)\r\n- *push* measures, which come when generated by the algorithm (e.g. when are new individuals generated?)\r\n\r\nBasically, the algorithm have no idea of when a *pull* can come, as it is decided depending on the needs of the external entities. At the opposite, the algorithm is the master when it comes to a *push*, because it is the one which knows when such a measure is feasible and generate it consequently.\r\n\r\nThinking about the code, I would model that with 3 interfaces:\r\n```java\r\npublic interface Measure {\r\n\t// Name of the measure, e.g. \"population size\"\r\n\tpublic String getName();\r\n\t// Description of the measure, e.g. \"Provide the current size of the population of individuals.\"\r\n\tpublic String getDescription();\r\n}\r\n```\r\nThis generic interface aims at centralizing the common \"administrative\" methods that a measure should provide. If you want a measure to be freed from these administrative work, then you can let the generic interface empty (but still present) and put these methods in an external interface like `NamedEntity`. This way, not only you can let the algorithms choose whether they implement or not this stuff (it is mainly needed for GUIs, so it is arguable to force a measure to implement them) and reuse it for other stuff (like algorithms themselves, problems, and so on, which would make sense for GUIs too). Thus, my recommendation would be the separation.\r\n\r\nThen, extending this generic interface:\r\n```java\r\npublic interface PullMeasure<T> extends Measure {\r\n\t// Request immediately the current value of the measure\r\n\tpublic T get();\r\n}\r\n```\r\n```java\r\npublic interface PushMeasure<T> extends Measure {\r\n\t// Register to obtain the measure when it is computed\r\n\tpublic void register(MeasureListener<T> listener);\r\n\t// Unregister to free the measure when it is not needed anymore\r\n\tpublic void unregister(MeasureListener<T> listener);\r\n}\r\n```\r\nThe former is trivial, but the latter uses a typical event-based pattern: the listener. You find it for instance extensively in Swing to manage the GUI's events (mouse click, keyboard button pushed, etc.). Thus, we come with this additional interface:\r\n```java\r\npublic interface MeasureListener<T> {\r\n\tpublic void measureGenerated(T value);\r\n}\r\n```\r\n\r\nConcretely, when an algorithm is measurable, it should provide the `Measure` instances such as:\r\n- a `PullMeasure` implement a `get()` which computes or retrieves the value and returns it\r\n- a call to the `register()` of a `PushMeasure` makes the algorithm stores the listener, and then call the `measureGenerated()` of each registered listener when the corresponding measure is generated. This is the responsibility of the external entities to implement the listeners to exploit these measures.\r\n\r\n**Why not having `Measure<T>`?**\r\nActually, you could think that a measure makes no sense without knowing the type of value it corresponds to. It seems to me justifiable, but here I did not put `<T>` to the root interface because no method actually needs it, thus I consider that \"with this definition\" such a concept (the type of value managed) is of no use and can be ignored. If you prefer to have it, you can add it, it will only change the extensions of the two other interfaces because `Measure` is not supposed to be used out of these extensions (algorithms should only implement pull and push variants, not the root interface). Additionally, if later you find a common method to add at the root level which needs to know the type of value managed, then you will already have it. So it can be considered as safer to have it from the root level.\r\n\r\n**If `Measure` is not supposed to be used, moreover if we delegate its methods to another more generic interface, why not having only the pull and push variants?**\r\nShortly speaking, as it is aimed to be used, it is just an extra, useless interface. The only argument I see is on the conceptual level: this way, you have a proper category which encloses pull and push measures together without mixing them with everything (the next level is `Object`). If for instance one wants to know whether an object is an instance of a measure, it can use the generic `instanceof Measure` rather than 2 checks, one for each variant. Basically, it is ontologically better, because more complete, but it is practically worst, because add code which is not aimed to be used. I am more on the ontological side, thus my choice. Feel free to choose one or the other.\r\n\r\n# Measurable algorithm & Measure manager\r\n\r\nBasically, as this is the algorithm which knows which measures can be applied on it, it has the responsibility of informing external entities about these measures. For instance, you can define such an interface to apply it to an algorithm:\r\n```java\r\npublic interface Measurable {\r\n\tpublic MeasureManager getMeasureManager();\r\n}\r\n```\r\nThis `MeasureManager` should be implemented by the algorithm depending on the measures it wants to provide:\r\n```java\r\npublic interface MeasureManager {\r\n\tpublic Collection<PullMeasure<?>> getPullMeasures();\r\n\tpublic Collection<PushMeasure<?>> getPushMeasures();\r\n}\r\n```\r\n\r\n**Why not having a simple `public Collection<Measure> getMeasures();`?**\r\nThe main argument is because an external entity is supposed to know whether a measure works on a *pull* or *push* mode, otherwise it cannot use it. If you use such a generic method, then a check of the different instances and their casting into the relevant pull/push interface becomes mandatory. You can save this mandatory effort by providing them separately with the right conceptual level. An additional argument could be that pull and push measures are generally managed in a completely different way, thus it makes sense to provide them separately to simplify the work, but from my point of view this is not an assumption, but a hypothesis or a common assertion (it is not assumed to be always correct, but generally correct) thus it should not have an influence on this interface. Rather, having some other entities which allows to simplify the work (making it a proper assumption for the specific class), like dedicated builders and factories, would make the deal without impairing on the conceptual robustness.\r\n\r\n**Why not extending the `Algorithm` interface?**\r\nThis can be done too. Question of design. If you think that measures in your framework make sense only in an algorithm, then you can replace `Measurable` by `MeasurableAlgorithm extends Algorithm<...>`. I said that \"it makes no sense out of the algorithm measured\", but actually you can generalize it as \"it makes no sense out of the entity measured\", as it is this entity which constrains what can be measured and what cannot (because does not exist in its context). This is like the administrative methods of `Measure`: is it better to have them specifically for a measure or independently available for others? The separation is generally safer, so if you are not sure prefer the separation in a generic interface. Nothing forbid you to implement a generic interface, but an algorithm implementing `Measure` just to have its methods, considering the misalignment of the names it is an evidence of poor design.\r\n\r\n# Performances\r\n\r\nA *pull* particularly fits measures which should be measurable at any time. Such measures would have almost no influence on the algorithm unless the external entities are particularly greedy in being updated about them. For a measure with immediate access, like the population size which is generally already stored somewhere, no particular attention seems to me necessary. Just have the corresponding method to be called when it is needed. In case of consuming computation, a trade-off could be preferred. I come to that point later.\r\n\r\nThe *push* measures, at the opposite, would be the most consuming measures, because it implies to generate them everytime they happen. You can optimize it by considering for instance whether or not a listener is registered, so no need to compute it if no listener is registered.\r\n\r\nRegarding the trade-offs: let assume that you design a pull measure which aims at computing the evaluations of all the individuals in the population and return the list of the evaluated values. In such a case, computation on the fly could be heavy, so one could seek for optimization, such as storing the results when an evaluation is done (like you store it into the solution itself). This way, when such a measure is pulled, you just browse your storage (solutions or whatever), retrieve the values, build your list and return it, avoiding the heavy computation of the evaluation (actually, avoiding recomputing it). The critics about this way to do is that your implementation becomes influenced by the way they are used. If you store these evaluations for the algorithm optimization, this is OK because the algorithm store data for its own use, thus it has full control on it and do not influence others, but if you store it because some external entities on which you have no control could use your measure in a way which influence your algorithm, then the separation of the responsibilities is broken: you are not supposed to assume anything inside your algorithm (and more generally object) regarding how external entities would use your algorithm (resp. object), otherwise you introduce biases in its implementation which makes it optimized for specific uses and less efficient for others (there is no free lunch). If you make specific implementations for specific uses, then it is fine, because these implementations are assumed to be used in such a context, so you can use them as assumptions in your implementation. But if you intend to have a generic implementation, avoid mix \"habits\" with assumptions. Habits' based implementations are genericity killers.\r\n\r\nA way to solve that is to let the management of such \"measure use\" optimization to the one which actually use them, for instance adding a *push* measure which gives the evaluation of an individual when it is done. This way, it is the responsibility of the caller to get this measure and optimize its use the way it needs it. Then, considering to keep the pull and the push or to reduce to the push is a design choice. If you keep only one, you force any external entity wanting the second to adapt to this one. It is not intrinsically bad, in the sense that you have potentially an infinite set of measures which can be applied, so you have to choose anyway. You cannot implement everything. Then, advanced users have to build on what is available. If you keep both, then you can add to the description of one of them that for frequent uses it is recommended to use this other measure, and for the other that for rare uses the first one can be used to simplify the work (in the Javadoc and in the \"administrative\" method `getDescription()`).\r\n\r\nNB: an algorithm can use its one `MeasureManager` internally, registering to its own *push* measures and requesting for its own *pull* measures. This is a way to centralize the functionalities, then it is a conceptual choice to use it this way or to consider that such a manager is for the exclusive use of external entities. In the latter, you do not need to think about internal uses to implement it, so you have less constraints (e.g. no need to consider subtle infinite loops), but you also cannot exploit its features and so need to introduce some redundancies if you need them also internally. Question of design.\r\n\r\nLast, but not least, the use of listeners. If an external entity registers a listener which makes some heavy computation, in a single thread program it means that your algorithm will wait for this listener to finish its work before to call the next one. And this algorithm will not come back to its own computation before it has finished to call all the registered listeners. This could have a significant impact on your execution time measures, and you have no control regarding the content of these listeners (and you are not supposed to have any from inside the algorithm). One way to deal with it, ugly but possible, is to provide your own execution time measure. By stopping the counting when you start the calls and restarting it after the last has finished, you can provide a cleaner measure. You could even make a common implementation which deals with that so you can reuse it in several algorithms. Another way, the most common probably, is to exploit multi-threading by launching all the calls in a pool managed in another thread. This is a lot easier, because there is already implemented stuff in Java for that, but you have less control on it. For instance, threads can be stopped to run other threads if there is not enough CPU cores to run all of them separately, and you don't have much to know when your algorithm's thread is stopped. You can manage priorities to some extents but I never used them, so I don't know how much you can control it. Another problem is the synchronization: you can reach an inconsistent state if a reading code is executed while a writing code is executing on the same variable. But this is typical multi-threading management, there is tools for that in Java.\r\n\r\nA typical recommendation in listeners is to ask to execute quick tasks, and for heavy tasks to delegate them to other threads. As long as such a recommendation is fulfilled, the impact should not be significant. But if you prefer to manage it somehow, the cleanest way I see now is to provide a measure which provides the time spent in measures management: a default implementation for `MeasureManager` which provides some methods to feed the measures and counting the time spent in these calls would make the trick without taking in charge additional responsibilities regarding the algorithm. As the manager is the one which provides the available measures (from the point of view of the external entity), it can freely add measures on its own and manage them without letting the algorithm knows about it (only the management of the measures provided by the algorithm are delegate to the algorithm).\r\n\r\nNotice, by the way, that my interfaces are designed for a multi-threading purpose: in a single thread, an external entity cannot call a `PullMeasure.get()` if the algorithm is still running. This method makes sense only if the algorithm is running in a separated thread and the external entity call `get()` during the algorithm execution (otherwise all the *pull* measures are done at the end of the algorithm execution). If you want to have a proper GUI which works smoothly, multi-threading is mandatory. With Swing, everything is already implemented, but otherwise you also have features provided by Java, like `Runnable` (simple call), `Callable` (call with a returned value), `Executors` (thread pool management) and `Future` (allowing to wait for the return of a `Callable` at the last minute or simply to do something else if it is still not finished).\r\n\r\n# Measures Building\r\n\r\nAnother interesting property of this architecture is to allow the building of new measures based on existing ones, and in particular switching between pull and push versions.\r\n\r\nFor instance, let assume you have a population-based algorithm, and you can add/remove individuals from it. The algorithm can provide 2 push measures, one when an individual is removed and another one when a new individual is added (the value can be the (group of) individual(s) removed/added). An external entity can then create a new measure based on these two to compute the population size:\r\n```java\r\npublic PopulationSizeMeasure implements PullMeasure<Integer> {\r\n  private int size = 0;\r\n  \r\n  public <T> PopulationSizeMeasure(PushMeasure<T> adding, PushMeasure<T> removal) {\r\n    adding.register(new MeasureListener<T>() {\r\n      public void measureGenerated(T value) {\r\n        size++; // size += value.size() for a Collection<T>\r\n      }\r\n    });\r\n    removal.register(new MeasureListener<T>() {\r\n      public void measureGenerated(T value) {\r\n        size--; // size -= value.size() for a Collection<T>\r\n      }\r\n    });\r\n    // there should have also the unregistering process to not keep\r\n    // obsolete measures which are not used anymore. This can be done\r\n    // by overriding finalize() in this case.\r\n  }\r\n  \r\n  public Integer get() {\r\n    return size;\r\n  }\r\n  // ...\r\n}\r\n```\r\nThis way, each time an adding or a removal is done, this measure is updated on real time. Then, you just call the `get()` method of this custom measure to get the population size when you want.\r\n\r\nMoreover, as illustrated in this example, you can transform a push measure in a pull measure: by memorising the last value, you can return it on demand. In the same way, you can transform a pull measure in a push one, for instance by setting a push frequency (for regular measurement) or by making it depend on another push measure (for synchronization).\r\n\r\nWith such a feature, algorithms just need to provide some core measures, all the others can be then implemented based on them. This is a good way to minimize the impact on the performances of the algorithm. On the other hand, an algorithm could have the possibility to provide an optimized version of a measure which can be provided only due to the algorithm implementation. For instance, if the population size is already stored by the algorithm (any standard `Collection` usually stores it for a O(1) access) it is probably more performant to access directly this storage rather than making a computation based on the additions and removals of individuals. Thus, an algorithm should provide the minimal set of measures, and optionnally some additional, optimized measures. All others can be created by the external entities depending on their need to measure specific properties.\r\n\r\n# Measure solutions rather than return them\r\n\r\nAnother potential use of these measures could be to return the solutions: rather than requesting for each algorithm to return a solution or a set of solutions, maybe it could be more robust to request them to provide a \"solution measure\".\r\n\r\nThe disadvantage of the `Solution execute()` or `Collection<Solution> execute()` is that we make the assumption that the algorithm always finishes its execution before to return the solution or set of solutions to consider. Although it makes sense in many cases, probably the vast majority and the most common cases, it seems quite naive to think that you always need to wait that the algorithm is actually finished before to have any information about the solution. In particular, an [anytime algorithm](https://en.wikipedia.org/wiki/Anytime_algorithm) is not always supposed to finish by itself. In particular if the point is to evaluate the quality of the solution before to decide whether or not more time should be used in the processing.\r\n\r\nTo deal with that, we could use this `Algorithm` content:\r\n```java\r\npublic interface Algorithm<...> {\r\n\tpublic void execute();\r\n\tpublic Measure getSolutionMeasure();\r\n\t// ...\r\n}\r\n```\r\nNotice that a common implementation which returns its solution(s), assuming you get it as a black box (e.g. from another project or by loading it as a plug-in), can be translated in this architecture easily with this generic-purpose wrapper:\r\n```java\r\n// The generic wrapper to run an algorithm supposed to return its solution(s).\r\npublic abstract class MyWrappedAlgorithm<A, S> implements Algorithm<...> {\r\n\r\n\t// The black box algorithm to run, recieved in the constructor\r\n\tprivate final A algorithm;\r\n\t\r\n\t// The listeners we will use because we want to use a PushMeasure here\r\n\tprivate final Collection<MeasureListener<S>> listeners = new HashSet<MeasureListener<S>>();\r\n\r\n\t// The measure which provides the listeners to call when the solution is\r\n\t// returned by the algorithm.\r\n\tprivate final Measure solutionMeasure = new PushMeasure<S>() {\r\n\t\t\r\n\t\tpublic void register(MeasureListener<S> listener) {\r\n\t\t\tlisteners.add(listener);\r\n\t\t}\r\n\t\t\r\n\t\tpublic void unregister(MeasureListener<S> listener) {\r\n\t\t\tlisteners.remove(listener);\r\n\t\t}\r\n\t\t\r\n\t\t// ...\r\n\t};\r\n\t\r\n\t// Instanciation of the wrapper on a specific algorithm\r\n\tpublic MyWrappedAlgorithm(A algorithm) {\r\n\t\tthis.algorithm = algorithm;\r\n\t}\r\n\t\r\n\t// Standard execution method. The same code works for any type returned by\r\n\t// the black box algorithm, including collections of solutions.\r\n\tpublic void execute() {\r\n\t\t// Execution of the algorithm and reception of the solution. For a\r\n\t\t// non-generic wrapper, this line would be replaced by the call of the\r\n\t\t// relevant function of the algorithm. Here, for genericity, we use an\r\n\t\t// abstract method aimed to be implemented at the instanciation of this\r\n\t\t// class, when we know which type of algorithm is wrapped and how to\r\n\t\t// execute it.\r\n\t\tS solution = executeAlgorithm(this.algorithm);\r\n\t\t\r\n\t\t// Pushing of the solution to the listeners.\r\n\t\tfor(MeasureListener<S> listener : listeners) {\r\n\t\t\tlistener.measureGenerated(solution);\r\n\t\t}\r\n\t}\r\n\t\r\n\t// Method to implement the actual call of the relevant method which executes\r\n\t// the black box algorithm (thus, in this method it is not a black box\r\n\t// anymore).\r\n\tpublic abstract S executeAlgorithm(A algorithm);\r\n\t\r\n\t// Measure which allows to be notified when the solution is provided,\r\n\t// which means basically just before execute() returns.\r\n\tpublic Measure getSolutionMeasure() {\r\n\t\treturn this.solutionMeasure;\r\n\t}\r\n}\r\n```\r\nThis example of use shows that such an architecture is more generic than a \"return-based\" one, as you can manage returned-based algorithms as well as non returned-based ones.\r\n\r\n**Why use `Measure` and not `PushMeasure` directly for `getSolutionMeasure()`?**\r\nBecause one could prefer to return a `PullMeasure`. It is quite straightforward to use a `PushMeasure`, because each time you improve your (population of) solution(s) is a relevant time to push such evolution to the listeners. However, if the process becomes complex enough so that there is many relevant occasions to make these pushes, such that it could have a significant impact on the performance  (e.g. highly frequent iterations) or make the management of these pushes complex and redundant (e.g. different parts of the algorithm leading to potential improvements, like an hybrid algorithm), the design choice could be to use a pull version to reduce the impact to what is requested by the external entities.\r\n\r\n**By using `Measure` we do not know if it is a pull or push version, so it makes it harder to use. No?**\r\nNot really, because whether you know exactly which algorithm you are using, so you just need to cast it the right way (1 line), whether you are using it in a generic purpose, and thus you know it is a pull or a push, but nothing else. Basically, in the latter case, you will decide whether you want a pull-based management (e.g. manual request from the user) or a push-based one (e.g. auto logging), then get the solution measure, identify whether it is a pull or a push version and translate it if it is not the version you want, like illustrated in the previous section."},"comment":{"url":"https://api.github.com/repos/jMetal/jMetal/issues/comments/77642331","html_url":"https://github.com/jMetal/jMetal/issues/26#issuecomment-77642331","issue_url":"https://api.github.com/repos/jMetal/jMetal/issues/26","id":77642331,"user":{"login":"matthieu-vergne","id":1774210,"avatar_url":"https://avatars.githubusercontent.com/u/1774210?v=3","gravatar_id":"","url":"https://api.github.com/users/matthieu-vergne","html_url":"https://github.com/matthieu-vergne","followers_url":"https://api.github.com/users/matthieu-vergne/followers","following_url":"https://api.github.com/users/matthieu-vergne/following{/other_user}","gists_url":"https://api.github.com/users/matthieu-vergne/gists{/gist_id}","starred_url":"https://api.github.com/users/matthieu-vergne/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/matthieu-vergne/subscriptions","organizations_url":"https://api.github.com/users/matthieu-vergne/orgs","repos_url":"https://api.github.com/users/matthieu-vergne/repos","events_url":"https://api.github.com/users/matthieu-vergne/events{/privacy}","received_events_url":"https://api.github.com/users/matthieu-vergne/received_events","type":"User","site_admin":false},"created_at":"2015-03-06T21:48:39Z","updated_at":"2015-03-06T21:48:39Z","body":"Sure, take your time. The safest way is to do it on each lowest level class, from the easiest to change to the hardest to change. Then move the `implements` to the parent class, check which measure makes sense to move to this level in order to make it available to all the child classes, and go ahead, one parent after the other, until you reach the `Algorithm` interface. This allows you also to maximize the practice and minimize the risk to forget measures. Of course, the main inconvenient is that it is the longest way towards generalization (full bottom-up)."}}